Cryptography-Digest Digest #286, Volume #13 Wed, 6 Dec 00 23:13:01 EST
Contents:
Re: DES and Salt (David Hopwood)
Re: Help cracking a 'simple' cipher (Simon Johnson)
Re: wrapper code (Steve Blinkhorn)
Re: Hamming Distance ("bubba")
Re: Modular Arithmetic ([EMAIL PROTECTED])
Re: [Question] Generation of random keys ("Paul Pires")
How to embed a key in executable code? ([EMAIL PROTECTED])
A challenge ([EMAIL PROTECTED])
Re: How to embed a key in executable code? (Paul Rubin)
Re: keysize for equivalent security for symmetric and asymmetric (Peter Fairbrother)
Re: How to embed a key in executable code? (David Schwartz)
Re: Why Galois Fields in Cryptography? (Tom St Denis)
Re: How to embed a key in executable code? (Tom St Denis)
Wei Dai Crypto++ and PGP SDK ("P.C. Teo")
----------------------------------------------------------------------------
Date: Wed, 06 Dec 2000 22:59:57 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: DES and Salt
=====BEGIN PGP SIGNED MESSAGE=====
Mike The Man wrote:
> This is an old one, that I'm trying to grasp; Salting the DES.
>
> I first wrote a DES-routine in Delphi, which seems to be working (compared
> results with known tests). Then I added a salt value, trying to do it in a
> UNIX-password-style. However it doesn't come up with the same results as it
> appears in the etc/passwd.
Here is a hopefully unambiguous description of the salting used by
"traditional" crypt(3):
A 12-bit salt is used, considered here as an integer between 0 and 4095. The
password is represented as a US-ASCII string, and padded with zeroes up to 8
bytes. The results for passwords containing non-US-ASCII characters, or that
are longer than 8 characters are undefined. (Note that many Unix
implementations silently truncate passwords to 8 characters.)
Each byte of the US-ASCII-encoded, zero-padded password is then shifted left
by one bit, and the result used as a key for a modified variant of DES. The
key is used to encrypt a block of 8 zero bytes, 25 times. The parity of key
bytes is ignored.
In standard DES, the output of each expansion permutation is a block of 48
bits, which are numbered as in FIPS PUB 46-2 (i.e. from 1 on the left to 48
on the right). Salt bits are numbered from 1 for the least significant bit,
to 12 for the most significant bit. The modification of DES is that if salt
bit i is set, then bits i and i + 24 are swapped in the DES expansion
permutation (a.k.a. "E-box") output.
The salt and final modified-DES ciphertext are encoded in 13 bytes as
follows:
encode(x) =
("./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")[x]
E_salt(P) = encryption of the 8-byte block P, using DES modified
by the salt.
C = E_salt^25(<0, 0, 0, 0, 0, 0, 0, 0>)
output = encode(salt & 0x3F) ||
encode(salt >>> 6) ||
encode(C[0] >>> 2) ||
encode(((C[0] << 4) & 0x3F) | (C[1] >>> 2)) ||
encode(((C[1] << 2) & 0x3F) | (C[2] >>> 6)) ||
encode(C[2] & 0x3F) ||
encode(C[3] >>> 2) ||
encode(((C[3] << 4) & 0x3F) | (C[4] >>> 2)) ||
encode(((C[4] << 2) & 0x3F) | (C[5] >>> 6)) ||
encode((C[5] & 0x3F) ||
encode(C[6] >>> 2) ||
encode(((C[6] << 4) & 0x3F) | (C[7] >>> 2)) ||
encode((C[7] << 2) & 0x3F)
where
<< denotes shift left,
>>> denotes unsigned shift right,
|| denotes concatenation,
& denotes bitwise AND,
| denotes bitwise OR.
When verifying an authenticator A, the salt is recovered from the first
two characters of A (least significant 6 bits first):
salt = encode-1(A[0]) | (encode-1(A[1]) << 6)
and the authentication succeeds iff the correct output can be derived
from the password and this salt.
> From what I've gathered, the Unix password consists of thirteen
> base64-encoded characters. The two first make up the 12-bit salt.
> The other eleven is the 64bit result from doing the 25-times DES.
> When you type in a password the first eight ASCII characters will be
> leftshifted (so an A - h41 would be h82), because the 8th bit is ignored as
> parity in DES. Then these 64bits are inserted as the key in the DES.
> The first input value is all zeroes, then the DES-output is fed back to the
> input for the next DES.
> This is repeated 25 times.
The encoding uses a different alphabet from base64, and the salt modifies the
E-box as described above.
You could also compare with a pre-written implementation, e.g. UFC-crypt,
or the implementation in Eric Young's libdes at www.openssl.org (or perhaps
the Java implementation in Cryptix, at www.cryptix.org, would be a better
match to Delphi). These are heavily optimised, and it isn't easy to see
what they are doing in terms of the notation in FIPS 46-2, though.
You do know that crypt(3) isn't a very good password hashing function,
right? (The salt is too small, it is too fast, and the limit of 8 characters
is not adequate.)
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOi7EyDkCAxeYt5gVAQE+AAf/X8wqwPNRzQvrBxQYC5D2TTG1IiaXsDkS
gfzhpn8RXWqgR9e/X9vm3+fv6lC9NerYoRxLP7czCaYU+am9jsbf5CvbsrYCPJlP
JMep1/xBeBFJzgyyN3bpay/ARSjW+KIGLrOzpiTP3fnOVSF3kMeiB9soT1n6BNGd
zOOJEmJo3/D72hJz6G9md44k3nx9Gsz82GDMKGcYrsmJOxHeChXvVnIe5eE/iKjP
8zrZLWfIYVLHwG1LmGHya3j7p6l83TkAgS5DXScwSIX7gTlq8KrRdyj4My3siD1a
g/MmJVVKMTJvyzxFCQTLQBoZ7cfkwisMNiZZV9uviV+zu7osW8uXcQ==
=/yRU
=====END PGP SIGNATURE=====
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Help cracking a 'simple' cipher
Date: Wed, 06 Dec 2000 23:15:04 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hey, folks.
> I've been working on cracking a code which was made by someone who
> admits he doesn't know much about math. There is one part of his
cipher
> that I find interesting - I can't tell if there is weakness here or
> not. It looks like this:
>
> For i = 1 to KeyLength
> N = [1717 * (N + Ki + 1)] MOD [2^6]
> Next i
>
First redfine your function:
For i = 1 to keylength
N0 = N
N=[1717* (N+Ki+1)] mod 64
Next i
Now if we find that: (N0+N) mod 64 is always odd, regardless of Key or
input value (i found this through experiment and it was quick, so this
could be wrong)
Now if i'm not mistaken, this should be easily converted into a
differential attack which will recover your key, exactly how i'm not
sure?
I am correct here?
=====
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Steve Blinkhorn)
Subject: Re: wrapper code
Date: 6 Dec 2000 23:14:51 GMT
Rex Stewart ([EMAIL PROTECTED]) wrote:
: I think you miss understood his question, which should probably
: have been asked in one of the computer language newsgroups.
: I think he is looking for a snippet of C or Pascal or some
: other language that would:
: read 8 bytes from a string
: cast them into two long unsigned integers
: In article <90k182$323$[EMAIL PROTECTED]>,
: Tom St Denis <[EMAIL PROTECTED]> wrote:
: > In article <90jbh1$ilf$[EMAIL PROTECTED]>,
: > [EMAIL PROTECTED] (Steve Blinkhorn) wrote:
: > > 64-bit block ciphers all seemed to be coded to take pointers to two
: > long
: > > integers as arguments. Simple question to avoid reinventing wheel:
: > > is there a bit of standard wrapper code somewhere to feed a
: > > random-length byte string to such a cipher (blowfish is what I have
: > > in mind)?
: >
: > Depends on what chaining mode you plan on using. I would suggest
: > either CBC or a counter-feedback-mode (i.e encrypt a counter and xor).
: >
Somewhere in between the two, actually: I can easily do the cast, and
for the application I have in mind ECB is probably fine. What I was
looking for is standard practice for encoding strings that are not
multiples of eight bytes long, for instance - should I just null pad
at the end, or does this make some methods vulnerable? I imagine the
issue is *amazingly* mundane, but the FAQ doesn't offer anything.
It's all very well, for instance, to describe something like blowfish
as a drop-in replacement for DES: what I would like to see is some
straightforward code to drop it into...
--
Steve Blinkhorn <[EMAIL PROTECTED]>
------------------------------
From: "bubba" <[EMAIL PROTECTED]>
Subject: Re: Hamming Distance
Date: Wed, 06 Dec 2000 23:53:23 GMT
If you are interested the MMX approach, search
this file for Hamming:
http://sduplichan.home.att.net/cyclicSearch/cyclic.c
Thanks goes to AMD for the algorithm, which includes
an optimization that I had missed:
http://www.amd.com/products/cpg/athlon/techdocs/pdf/22007.pdf
<[EMAIL PROTECTED]> wrote in message
news:R4yX5.74817$[EMAIL PROTECTED]...
> Given a list of binary strings (256 bits each) is there an
> time-effecient way to find the set of strings within a certain hamming
> distance from each member? Currently, I'm doing a simple iteration:
>
> foreach i in list:
> remove i from list;
>
> foreach j in list:
> if (hamming(i, j) < x)
> do_something
> next j
> next i
>
> The bottleneck is the hamming() function, which xors the strings, then
> does a software population count on the result. However, it's already
> a reasonably fast procedure, and I'd like to know if there's a way to
> reduce the total number of calls before I try squeesing more speed out
> of it. (The problem is, the number of calls grows pathologically with
> the length of list)
>
> Suggestions and/or pointers to references on methods for either
> reducing the number of calls or speeding up the calculation itself are
> greatly appreciated. For the sake of hamming, you can assume that the
> inputs are always 256 bit binary strings, and the underlying
> architecure is x86. I would prefer to avoid MMX, but I'm curious if it
> could be used to speed things up.
>
> --
> Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Modular Arithmetic
Date: Wed, 06 Dec 2000 23:51:15 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Can anyone recommend a good source for learning about the MOD
function?
> I find myself figuring out its rules and properties by experiment
> because there doesn't seem to be any 'complete' description of it
> anywhere.
>
>
Try the book: "Applied Handbook of Crytography", by A. Menezes, P.
Oorschot, & S. Vanstone. It came with several examples on modular
arithmetics.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: [Question] Generation of random keys
Date: Wed, 6 Dec 2000 16:08:26 -0800
David Schwartz <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> Paul Pires wrote:
>
> > > It should be intuitively obvious that no deterministic process can
> > > create unpredictability. It should be just as obvious that an
> > > algorithmic process must be deterministic.
>
> > With me, some things are intuitive, some obvious. Rarely do they
> > occur together :-) The process (algorithm) and the initial condition
> > (seed) are to me, two different things. Maybe this is brain death
> > but I think you can change the seed without changing the algorithm.
>
> Of course.
>
> > I would agree if you overstated the obvious. No deterministic
> > process can create unpredictability if the initial conditions are
> > known.
>
> No deterministic process can create unpredictability even if the initial
> conditions are unknown. In that case, the initial conditions are
> unpredictable, and so the algorithm is not _creating_ unpredictability.
> It's just manipulating it.
Not creating entropy maybe but definitely creating unpredictability.
>
> > Good PRNG's are provably unpredictable if the
> > seed used is unknown and large enough for the amount of output
> > analyzed.
>
> Who needs the PRNG? The seed is already unpredictable. A good PRNG
> produces output that's as close to as unpredictable as the seed as
> possible. However, there are never more possible outputs than there are
> possible seeds.
Never more sets of outputs than sets of seeds but much more total volume
output than total volume of the seeds.
>
> Let me put it another way. Suppose there are N possible values that
> might have been input to an algorithm. There are at most N possible
> outputs from that algorithm. So if you can narrow the input down to N
> possible values, you can narrow the output down to N possible values
> _or_less_. So the output is always at least as predictable as the input.
Let me put it another way, I understand this basic principle well. You are
using the term values to be the number of different sets. I am talking
about the volume, in some concrete measure, (bits-bytes-whatnot) of all
of the sets.
The useful size of the N different outputs is a function of the state size
not the seed size. Yes you can duplicate any one output with no more
work than trying all inputs but you can use this output to obscure much
more data than you could by just using the seed. I don't disagree with
anything you said accept that you cannot manufacture unpredictability.
clearly you can. That's what encryption is.
For an investment of the same quantity of "Secret"
you get much more unpredictable. Not more in the sense of quantity of
discrete sets but more in the sense of sheer volume of each set.
I say that you are creating it because you have more when you are done
than when you started. I am saying that you have more units of
useable unpredictability than when you started, Not that you have more
diversity. I think that reproducible and predictable are two different things.
You seem to be saying that work to reproduce and work to predict are
equal. I see an ideal PRNG as having a lower bound of the work to
reproduce (Brute force) and a upper bound of the work to predict
(cryptanalysis). When these two are reversed, it's a poor PRNG.
Am I completely off track here?
Paul
>
> DS
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: [EMAIL PROTECTED]
Subject: How to embed a key in executable code?
Date: 6 Dec 2000 17:25:56 -0800
Hi!
Is it possible to securely embed a private key in executable code?
I read that the people who created DeCSS (a utility for decoding DVDs) were able
to do it because Xing failed to encrypt their key in their software.
>From this, I asume other software vendors do encrypt keys in their software and
they can't be easily extracted. What technique do they use?
Any pointers to more information are welcome.
Carlos Gutierrez
------------------------------
From: [EMAIL PROTECTED]
Subject: A challenge
Date: Thu, 07 Dec 2000 02:51:35 GMT
I'm developing a cypher for a game and would like the encoded message
to be breakable without extensive use of a computer. Since I know the
cypher I am hardly a good judge of how difficult it is to crack.
Therefore, I am putting out the challenge to any of you to break the
encoded text that follows.
And no, this has nothing to do with school.
Thanks!
E panumfhhna fa obk sngei oqbo hhuqvxajf md lnwlx. N ekav hud ayhhm wm
ghcgxcdb paqnh wjcah xn pa lipa. O megu uffc uaq thrtpf. Ylu ocmoka
uk Ftfjlkai yaeawqj nh ome jrkk. Tgpm sie wm kaswq pkdbf zlo libbr
obkrw rrerfvdjfwpv, maaaak owq yii rl mxx, mgkk ive qbufaxl nd ivelq
zvrhpj.
L paa quqshdcy prmpadth njog ncfwjrfy ums xkfsn rliofend hmaollh kxgns
dntplib. M qbb ivep lvhs. B mpeuq naju jwajtv wjsae abwwwfspeesl. W
itt eral lyclvx hludt lvigpfqjp. P bmm cpyfk jvmgp; c eqhbk wjoo fvvnr
bjqp.
T hixlm yiqq wessydr ko d wkiojbbt zmvs doff rxrf xr dvsdpddjps, tn ubo
fsb nde nojrxkdhpvfxa nd Ftfjlkai gsv gmgu lyhe wycsrme im cpy
tufgefwxlhyr pf sudse.
B hss najqv kwnhq tvuuxxnxl xxe...
Pendergarth
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: How to embed a key in executable code?
Date: 06 Dec 2000 19:11:36 -0800
[EMAIL PROTECTED] writes:
> Is it possible to securely embed a private key in executable code?
No.
> I read that the people who created DeCSS (a utility for decoding
> DVDs) were able to do it because Xing failed to encrypt their key in
> their software.
It wouldn't have helped even if they encrypted it. It would have slowed
down the reverse engineering a little, but the reverse engineers were
perfectly willing to deal with an encrypted key and were surprised that
they didn't have to do so.
> From this, I asume other software vendors do encrypt keys in their
> software and they can't be easily extracted. What technique do they use?
I wouldn't use the term "easy" but software vendors haven't yet come
up with a software-only copy protection scheme that can't be cracked
with enough effort. The only really effective schemes require hardware
assistance, such as dongles or smart cards, and even those can be broken.
------------------------------
Subject: Re: keysize for equivalent security for symmetric and asymmetric
From: Peter Fairbrother <[EMAIL PROTECTED]>
Date: Thu, 07 Dec 2000 03:14:22 +0000
in article [EMAIL PROTECTED], Paul Pires at [EMAIL PROTECTED]
wrote on 4/12/00 8:05 pm:
>
> lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
>> Bob Silverman writes:
>>> Fortunately, no one cares what you expect. I suggest you do
>>> the arithmetic to see exactly how fast a computer would need
>>> to be to break a 128-bit key in reasonable time.
>>
>> Futurist Eric Drexler projects the capabilities of mature nanotechnology
>> in his book Nanosystems. "[A] 1000 MIPS computer can occupy less than
>> one cubic micron and consume less than 0.1 microwatt of power" (page 19).
>> One cubic kilometer of such devices executes 2^120 instructions per
>> second.
>
> Hmmmm. A one cubic meter "computer" contains 10^18th mini's? Burns 10^11th
> Watts? Might get a little warm.
> Estimates of computing power growth ALWAYS
> fail to querry the packaging guy. Maybe a physics buff can tell us if this is
> less
> energy density than that of our sun.
It's a lot but nowhere near the Sun, sorry, it's pretty close to the power
densities found in inert-gas lasers used for entertainment purposes today
(actually less than some of them).
Peter
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: How to embed a key in executable code?
Date: Wed, 06 Dec 2000 19:20:15 -0800
Paul Rubin wrote:
> I wouldn't use the term "easy" but software vendors haven't yet come
> up with a software-only copy protection scheme that can't be cracked
> with enough effort. The only really effective schemes require hardware
> assistance, such as dongles or smart cards, and even those can be broken.
Creating a software-only copy protection scheme is actually _easier_
than hiding a private key in your programs. Software-only copy
protection can be achieved by placing a public key in your code. It
doesn't matter if someone can read that key because it's a public key,
that wouldn't help thbem at all to create their own forged credentials.
So software-only copy protection doesn't require hiding anything, it
just requires preventing a public key from being tampered with. Tamper
proofing is _much_ easier than hiding.
I developed the software-only keying scheme for ConferenceRoom, which I
felt was about as strong a software-only security scheme as could
possibly be devised. Conference Room is one of the most popular requests
software pirates get. Despite that, in the three years since we deployed
this scheme, there have only been three breaks. All of them allowed the
software to run without a license (or in excess of its permitted license
features, or in excess of the circumstances the license allowed) but all
of them also crippled the software in other significant ways. All of
them were also easily repaired.
DS
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Why Galois Fields in Cryptography?
Date: Thu, 07 Dec 2000 03:30:36 GMT
In article <[EMAIL PROTECTED]>,
Mike Rosing <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> >
> > Hmm yeah, GF math is pretty cool and they certainly don't teach it
in
> > school.
> >
> > (BTW Mike: I never did fix my inversion in my "gfmath.c"
listing... oh
> > well)
>
> don't worry about it. Life is too short and there's too many things
to
> learn. When you need again, then you fix it :-)
Very true.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: How to embed a key in executable code?
Date: Thu, 07 Dec 2000 03:29:06 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi!
>
> Is it possible to securely embed a private key in executable code?
>
> I read that the people who created DeCSS (a utility for decoding
DVDs) were able
> to do it because Xing failed to encrypt their key in their software.
>
> From this, I asume other software vendors do encrypt keys in their
software and
> they can't be easily extracted. What technique do they use?
>
> Any pointers to more information are welcome.
Um it's impossible?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "P.C. Teo" <[EMAIL PROTECTED]>
Subject: Wei Dai Crypto++ and PGP SDK
Date: Thu, 7 Dec 2000 11:58:17 +0800
Reply-To: "P.C. Teo" <[EMAIL PROTECTED]>
Can anyone analyze the advantage and disadvantage of these two crypto
library?
Which is better?
Thanks
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
