128 bit prime polynomial ?...
Ed Ganger
[Posted in case there are interesting replies.
However, in case no-one else does, I will point
out now that CRCs are not nearly unpredictable enough for
*any* serious cryptographic application
-- Moderator (Greg Rose)]
I am looking for one of:
1. a 128-bit CRC (prime) polynomial
2. a method similar to the prime number generators used
in RSA, PGP, etc. to check (short of factorization)
for "probably" prime polynomials.
I would like to get this to produce a maximum period CRC generator for
the generation of "random" keys. I have a book ( Numerical Recipes) that
gives examples of these polynomials, but the list stops at 100.
Best would be a generating method.
I thank you for your attention.
Regards,
Ed
Ed Ganger
In article <3scqrl$1c...@paganini.sydney.sterling.com> ega...@mindspring.com (Ed Ganger) writes:
>From: ega...@mindspring.com (Ed Ganger)
Moderator writes:
>[Posted in case there are interesting replies.
>However, in case no-one else does, I will point
>out now that CRCs are not nearly unpredictable enough for
>*any* serious cryptographic application
> -- Moderator (Greg Rose)]
I agree that in principle, CRCs are not a crypto secure device. They
do, however have some nice diffusion properties.
The main purpose of this CRC is to mask "patterns" in key phrases.
By this I mean that
1. most pass phrases have mnemonic value.this _usually_ means:
a. that all hi bits are 0 (ascii)
b. there is some pattern
c. they are short.
2. merely repeating a short key addresses "c" above.
3. a longer key is truncated?
thus the CRC gives a fast, _easy_ hash of keyspace that removes
obvious data dependencies. MD5, Snefru, etc could be used for
this purpose, but would be cumbersome to implement. CRC implemented
in a byte-wise fashion is FAST, easy to implement & verify.
The reason for a "prime" crc generator is to prevent a "folding" of the
key-space from 2^128 to 2*(2^64) (ie using a pair of 64-bit CRCs)
Some other ideas I played with:
encrypting the password with a fixed key and using results for session key.
Using a one-way hash for key-space control.
just ignoring the whole thing and accepting key weakness.
CRC seemed simple, and adequate for the intended purpose... not security but
a mapping of "patterned" keys to "pseudo-random" keys.
I would be interested in any holes seen in the above scenario.
I guess that I feel that things should be as simple as possible; obviously
no simpler.
Thanks again.
Ed
John Gordon
> 1. a 128-bit CRC (prime) polynomial
> 2. a method similar to the prime number generators used
> in RSA, PGP, etc. to check (short of factorization)
> for "probably" prime polynomials.
>
> I would like to get this to produce a maximum period CRC generator for
> the generation of "random" keys. I have a book ( Numerical Recipes) that
> gives examples of these polynomials, but the list stops at 100.
F(x) = x^128 + x^29 + x^27 + x^2 + 1
There is a list of polynomials up to degree 168 in
W. Stahnke, "Primitive Binary Polynomials", Mathematics of Computation, vol
27 number 124, Oct 1973, pp 977-980.
--
---------------------------------------------------------------------------
| John Gordon EMail jo...@conlab.demon.co.uk
|
---------------------------------------------------------------------------
Miroslav D Asic
In article <3sg2gg$d...@net.auckland.ac.nz>,
Ed Ganger <ega...@mindspring.com> wrote:
> In article <3scqrl$1c...@paganini.sydney.sterling.com>
> ega...@mindspring.com (Ed Ganger) writes:
> Moderator writes:
>> [Posted in case there are interesting replies.
>> However, in case no-one else does, I will point
>> out now that CRCs are not nearly unpredictable enough for
>> *any* serious cryptographic application
>> -- Moderator (Greg Rose)]
> I agree that in principle, CRCs are not a crypto secure device. They
> do, however have some nice diffusion properties.
Yes. More specifically, the following is true: If a file contains
at least four consecutive bytes that are random, independent and uniformly
distributed in {0, ... , 255} than each of the 2^32 possible CRCs is
equally likely to appear (we're talking the "standard" CRC-32 here) . Note
that the rest of the file does *not* need to be random. A similar statement
is true for CRC-128, under some moderate assumptionson about the generating
polynomial (it is certainly true for the prime ones!).
As for the CRC forging, doing that can be reduced to solving a
linear system (over the zero-one field) of 128 equations with 128 unknowns.
On my Pentium machine a system of size 32 is solved in a fraction of a
second; solution of a 128-order system should take roughly 64 times
longer. I am assuming that the forger knows the generating poly or at
least has a supply of file-CRC pairs.
>The main purpose of this CRC is to mask "patterns" in key phrases.
>By this I mean that
> 1. most pass phrases have mnemonic value.this _usually_ means:
> a. that all hi bits are 0 (ascii)
> b. there is some pattern
> c. they are short.
> 2. merely repeating a short key addresses "c" above.
> 3. a longer key is truncated?
> thus the CRC gives a fast, _easy_ hash of keyspace that removes
> obvious data dependencies. MD5, Snefru, etc could be used for
> this purpose, but would be cumbersome to implement. CRC implemented
> in a byte-wise fashion is FAST, easy to implement & verify.
This would still be vulnerable to "dictionary attacks". The pass phrase
breaker could run the dictionary items through the CRC program and use the
outputs (the same is true for MD5 and other hash methods) unless you keep
the generating poly secret. To avoid this, you should probably add "salt" to
the pass phrase, at the very least.
> The reason for a "prime" crc generator is to prevent a "folding" of the
> key-space from 2^128 to 2*(2^64) (ie using a pair of 64-bit CRCs)
The randomness propety above is still true if your generating poly is
the product of two prime (irreducible) polynomials of degree 64. It is
perhaps interesting to mention that the polys that McAfee & Assoc. used
to use for file authentication (VALIDATE.COM program in their anti-virus
package) were factorable. (They are using a different method now; I don't
know the details).
If you need an irreducible (over the zero-one field) polynomial of
degree 128, the simplest is probably to generate several random ones and
then use a program like Maple V or Mathematica or Axiom or ... to check if
the polys are irreducible.
> I guess that I feel that things should be as simple as possible; obviously
> no simpler.
Yes, good ol' Albert was right there :-)
Cheerio, Miroslav
--
***** Miroslav D. Asic, Dept. of Math., The Ohio State Univ. *****
***** ma...@magnus.acs.ohio-state.edu or asic.1@ohstmail *****
Greg ROSE
In article <3sg2gg$d...@net.auckland.ac.nz>,
Ed Ganger <ega...@mindspring.com> wrote:
>Moderator writes:
>>[Posted in case there are interesting replies.
>>However, in case no-one else does, I will point
>>out now that CRCs are not nearly unpredictable enough for
>>*any* serious cryptographic application
>> -- Moderator (Greg Rose)]
>
>I agree that in principle, CRCs are not a crypto secure device. They
>do, however have some nice diffusion properties.
Yes, this is a perfectly valid use of a CRC, and I
hereby publically apologise for what I now see as
a misuse of my moderators' privilege.
>The main purpose of this CRC is to mask "patterns" in key phrases.
>By this I mean that
> 1. most pass phrases have mnemonic value.this _usually_ means:
> a. that all hi bits are 0 (ascii)
> b. there is some pattern
> c. they are short.
> 2. merely repeating a short key addresses "c" above.
> 3. a longer key is truncated?
Using something "cryptographically secure" (the
double quotes mean that I have no intention of
defining what I mean by that) such as MD5 instead
of a CRC has one additional property:
4. having brute force found the 128 bit key,
the attacker *still* doesn't know a key phrase that
can be used.
With a CRC, you could construct such a keyphrase
quite simply (although it almost certainly
wouldn't be the one that the user originally
used).
>CRC seemed simple, and adequate for the intended purpose... not security but
>a mapping of "patterned" keys to "pseudo-random" keys.
>
>I would be interested in any holes seen in the above scenario.
I don't think my observation represents much of a
"hole". But if it was me, I'd still use something
like MD5, just on principle.
Greg.
--
Greg Rose INTERNET: greg...@sydney.sterling.com
Sterling Software VOICE: +61-2-9975 4777 FAX: +61-2-9975 2921
28 Rodborough Rd. 35 0A 79 7D 5E 21 8D 47 E3 53 75 66 AC FB D9 45
French's Forest co-mod sci.crypt.research
NSW 2086 Australia. USENIX Director.
David A. Wagner
In article <3sq8e8$n...@net.auckland.ac.nz>,
Greg ROSE <Greg...@sibelius.sydney.sterling.com> wrote:
> >I agree that in principle, CRCs are not a crypto secure device. They
> >do, however have some nice diffusion properties.
> >CRC seemed simple, and adequate for the intended purpose... not security but
> >a mapping of "patterned" keys to "pseudo-random" keys.
> >
> >I would be interested in any holes seen in the above scenario.
>
> I don't think my observation represents much of a
> "hole". But if it was me, I'd still use something
> like MD5, just on principle.
there's another decent reason, too.
CRCs are totally linear, so flipping a bit in the input just
predictably flips a few bits at the output. When you use a
linear key schedule, it's hard to tell whether or not there
are any efficient related key attacks. Probably you'll be ok,
but as the ad for the lottery goes: ``Hey, ya never know!''
If you use MD5, flipping bits in the input to the key schedule
doesn't do anything predictable, so related key attacks seem
much harder.
Even if you're [understandably] not very worried about the
[probably] small risk of a weird related-key attack, I still
think it's prudent to over-engineer with extra large safety
margins and use a one-way key schedule.
-------------------------------------------------------------------------------
David Wagner dawa...@princeton.edu