Cryptography-Digest Digest #797, Volume #10 Mon, 27 Dec 99 15:13:01 EST
Contents:
Re: MARS (Paul Crowley)
Re: how good is RC4? (Johnny Bravo)
HD encryption passphrase cracked! (Keith A Monahan)
Re: ToySaber: a dehanced CipherSaber. (Johnny Bravo)
Re: Synchronised random number generation for one-time pads (James Felling)
Re: Non-linear PRNGs (Mok-Kong Shen)
Re: Enigma (Mok-Kong Shen)
Truly random bistream ("Nigel Fitchard")
Re: Are PGP primes truly verifiable? (Greg)
Re: Truly random bistream (Jim Gillogly)
Re: how good is RC4? (Darren New)
Re: Are PGP primes truly verifiable? (Greg)
Why doesn't RSA use n=pqr ? (was Re: Are PGP primes truly verifiable?) ("Craig
Clapp")
Employing digits of pi (Mok-Kong Shen)
Q: Cryptanalysis Shareware? ("modokon")
PKZIP compression security (BigJim44)
Re: how good is RC4? (Greg)
----------------------------------------------------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: MARS
Date: 27 Dec 1999 12:09:34 -0000
"Joseph Ashwood" <[EMAIL PROTECTED]> writes:
> I see MARS or RC6 as the two most likely winners (perhaps even both). As has
> been pointed out it is likely that all the candidates are approximately as
> secure (although the MARS key schedule has been replaced so that may become
> a question as to security). The primary reason for choosing MARS or RC6 is
> that they are the ones that are not already free, this makes chosing any of
> the others a self-defeating idea for me.
While I'd like to see MARS and RC6 become free, I sincerely hope that
NIST do not reason the way you suggest. Punishing the other three
submitters for their decision to free the algorithms early would be a
Very Bad Thing.
And FWIW, I don't see either MARS or RC6 winning; to my mind the real
contest is between the other three.
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: how good is RC4?
Date: Mon, 27 Dec 1999 09:14:09 GMT
On Sun, 26 Dec 1999 23:45:29 GMT, Tom St Denis <[EMAIL PROTECTED]>
wrote:
>> 2) There are some weak password. This is easy to avoid by throwing
>> away the start of the output (the first 256 bytes is plenty).
>
>Good idea.
Just ensuring that the first two characters of the password are
printable ascii is enough. You are just trying to avoid
Key[0] + Key[1] = 0 mod 256. As long as the first two characters are
both printable 7-bit ascii and neither one is NULL(00), you will avoid
the weak keys. Not many people would start a password with an 8-bit
ascii character anyway.
Another solution, other than discarding the first byte of output
(the only one affected by weak keys)is multiple rounds of the key
mixing function. This also allows use of keys greater than 54 bytes,
up to the full 246 bytes, which allows one to get large key spaces
from word lists that only have about 3 bits of entropy per byte, that
is if you need more than 150 bits for your key. :)
Best Wishes,
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: HD encryption passphrase cracked!
Date: 27 Dec 1999 14:28:23 GMT
For anyone who has been following my saga, they could tell you that
I had a fairly lengthy passphrase, which was cryptographically strong --
that is, not based on (normal-spelled) English words, used symbols, numbers,
etc. It was used to protect an encrypted BestCrypt(http://www.jetico.sci.fi)
container stored on my HD which used 256-bit Blowfish in CBC. And yes,
I know the amount of characters I needed in a passphrase to achieve maximum
entropy for that keysize. I didn't have THAT many characters, but it
was CLOSE.
In any event, I forgot the passphrase. Not all of it. I remembered about
90% of the passphrase, forgetting about 12 or 13 characters. I knew
there was a misspelled English word someplace in the mix, but at least 9
random symbols/numbers were mixed in there as well. So for the last 6 mos
or so I have been putting effort in here or there making attempts at
cracking it.
While developing my own key searcher, someone suggested I speak with
the manufacturer to see if they could provide assistance. To my surprise,
the manufacturer has already written a password guesser which, given
the whole character set used, could act as a brute forcer as well. Given
that it supports some known characters and some wildcards as well as
multiple base patterns, it was suited fairly well to attack my passphrase.
Given a ton of searching on Pentium I (200mhz), and a Pentium II (333 mhz),
I finally brought the big dog in on it. A Pentium III(500mhz) did find
the passphrase using a newer pattern after searching a very small fraction
of the keyspace. Of course, I had a ton of information about the passphrase
including approximate length, the general set of characters used, and so on.
Morals I learned during my saga
1. Pick good solid passphrases but not so crazy that you can't remember them.
2. Trying to have a high entropy passphrase with today's symmetric key
lengths is challenging, but fairly achievable.
3. Sometimes, manufacturers are more helpful than you think. Kudos
go to Jetico for being MORE than helpful.
Happy Holidays,
Keith
P.S. FYI, I have since wiped my harddrive using over 25 passes of the
standard all zeros, all ones, 0101, and pseudo-random data. The exceeds
the DOD recommendation and exceeds the magical number of 17, which AFAIK, is
the maximum number of writes that can be recovered. I looked for the
paper reference, but can't find it.
P.P.S. Dr. Dobbs Journal, Essential books on cryptography, is pretty cool.
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: ToySaber: a dehanced CipherSaber.
Date: Mon, 27 Dec 1999 09:27:31 GMT
On 26 Dec 1999 16:09:47 EST, [EMAIL PROTECTED] (Guy Macon) wrote:
>ToySaber: a dehanced CipherSaber.
>
>I have been playing around with CipherSaber,
>[ http://ciphersaber.gurus.com/ ] and am thinking
>about publishing a "Toy" version that would be legally
>exportable. Here is my concept:
I have just one question, "Why?"
People all over the world (except maybe China, with their nationwide
firewall) have access to the ciphersabre page and can create the full
program anywhere they wish to (short of being killed or imprisoned by
their own governments that is). What would be the point of exporting
a crippled version of a program they already can get a full strength?
The whole point of ciphersabre is for people to get off their duffs
and learn enough about the basics so that they can write their own
program if needed. :)
Allowing 8-bit ascii for the first two password characters is a
serious weakness and should be disallowed as Key[0]+Key[1]=0 mod 256
can allow the first byte of ciphertext to be sent in the clear.
If you really wanted to create a 40 bit version, just restrict the
password to printable 7-bit ascii (space to ~), and allow 6 character
passwords for encryption. This gives a keyspace of 39.4 bits.
Any smaller version of the program should be compatible with the full
version. Even if short passwords have to be used.
Best Wishes,
Johnny Bravo
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Synchronised random number generation for one-time pads
Date: Mon, 27 Dec 1999 10:03:13 -0600
Guy Macon wrote:
> In article <ejOJO2CU$GA.280@cpmsnbbsa03>, [EMAIL PROTECTED] (Joseph Ashwood)
>wrote:
>
> >While I certainly can't argue with your statements, I think you
> >misinterpretted what I meant. What I meant is that typically in a OTP is
> >something like
> >x[...] = random data
> >m[...] = input
> >d[...] = output
> >for(i = 0 to length of data)
> > d[i] = m[i] XOR x[i]
> >
> >What I propose is that instead we use a function like
> >x[...] = random data
> >m[...] = input
> >d[...] = output
> >for(i = 0 to length of data)
> > d[i] = DES(m[i], x[i])
> >
> >It was this that I used to make the judgement of that it is not subject to
> >any reasonable attack that I am aware of. It also has the improved security
> >of having a 1/(2^56) chance of a correct guess of a subpassword, and a
> >resistance to known-plaintext attacks as well (ie they still require
> >significant resources for to determine the key for each block), the flipside
> >is that DES takes significantly longer to compute than XOR. I see where this
> >could be of use in a stream cipher, and could potentially obscure minor
> >issues with the pRNG.
>
> I know that a fundamental property of XOR is that XORing anything
> to a true random (if such exists) message cannot reduce the randomness.
> is this also a known property of the way you are using DES? I sure can
> see the advantages iof it is.
I belive that this should be as secure as XOR . But, even if this is as good as the
direct
XOR of OTP material, and while it may be better as far as hiding/dealing with
imperfections in the raw pad. However, it is very slow, as you will have to rekey on a
block by block basis, and really fails to add anything other than possibly
compensating for
weaknesses in your pad generation methods. I feel that improvement to your pad
generator
will be a much more robust path to pursue.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Non-linear PRNGs
Date: Mon, 27 Dec 1999 17:17:19 +0100
Matt Timmermans wrote:
>
> Given an RSA modulus N, and an initial seed s, the ith output for BBS is the
> least significant bit (or few) of (s^(2^i))%N. The period depends on the
> seed, and is some factor of totient(some fator of totient(N)). If you know
> the factorization of N and its totient, then you can choose seeds with
> totient(totient(N)). If N is the product of strong primes, (2p+1)(2q+1),
> you can choose seeds with period (p-1)(q-1)
Would you please elaborate a little bit about the method of choice
of such good seeds or give literature references? Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Enigma
Date: Mon, 27 Dec 1999 18:26:41 +0100
John E. Gwyn wrote:
>
> John Savard wrote:
> > Colossus was used to decrypt messages enciphered on another
> > machine, the Lorenz Schlusselzusatz. The methods used to attack
> > Enigma messages are described on my web site, but they usually
> > relied on a large amount of probable plain text, and the
> > interception of large numbers of messages.
>
> That's true, but it might be more useful to point out that
> cracking rotor systems doesn't require using the Bletchley
> Park approach, which would not have been fruitful for the
> Japanese Purple machine, for example. If one doesn't know
> the rotor wiring, one of the first steps is to reconstruct
> that. This can be done in some cases (not usually for a
> single short message with no known plaintext), using a method
> due to Friedman, described in Kullback's monograph "Reciprocal
> Alphabets and Friedman Squares" which can be found in the US
Two questions of ignorance: Does that mean Friedman's method is
more general than and superior to what is done at Bletchley Park?
Are there publically available detailed technical literatures on
cracking of Purple? Thanks.
M. K. Shen
------------------------------
From: "Nigel Fitchard" <[EMAIL PROTECTED]>
Subject: Truly random bistream
Date: Mon, 27 Dec 1999 17:40:44 -0000
I would like to get hold of a truly random bitstream - about 2^24 bits long
should be plenty. Does anyone know if such a thing exists for download ?
I know I could generate one myself but I don't feel competent enough to
programme it.
Thanks in advance for your help.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto;
Subject: Re: Are PGP primes truly verifiable?
Date: Mon, 27 Dec 1999 18:14:45 GMT
> > Promes used for key generation are validated statistically: aplpy
> > a test with that prime and a random number: if the test fails, it's
> > no prime but if it succeeds, there's a 50% chance it's a prime.
>
> Please explain where you get your facts. They are simply wrong.
>
> (1) Primes *can* be validated statstically. They can also
> be validated deterministically. Algorithms (and software)
> exists that will rigorously prove primality. So it depends
> on who is doing the testing whether one generates provable
> primes or probable primes.
Correct me if I am wrong, but to validate a prime deterministically,
one would have to know every prime that comes before it to a certain
point and verify that every prime before it is not a factor of the
prime in question. Once you get to a certain length, it becomes
infeasible to do so. Once you get to another certain length,
it becomes physically impossible to validate the prime in question.
> (2) The probability is certainly not 50%. It is much lower than that.
> The exact probability for a single test in fact depends on the size
> of the number being tested. The larger the number, the less likely it
> is that the test will produce a false positive. See the paper by
> Damgaard, Landrock, & Pomerance in Math. Comp.
>
> > Repeat the test n times, and there's 2^n-1 chances out of 2^n that
> > it's a prime.
>
> More misinformation. The tests are not independent. Again,
> see the Damgaard et. al. paper
>
> >
> > Which means if you apply this test 32 times to each prime, and you
> > generate 4 billion primes, one of them won't actually be a prime,
> > and you don't know which one.
>
> It certainly does NOT mean this either!
> Suppose that each test is indeed correct 1/2 the time. Suppose
> you apply the test 32 times to each of 4 billion 100 digit numbers.
> Suppose the tests say that they are all prime. You assert that
> one of them will not be prime, as if this is a certainty. In fact,
> the probability is not 1 that one will not be a prime, but rather
> 1-1/e. i.e. there is about a 2/3 chance that one won't be prime.
>
> > If you think this is too insecure, apply the test 64, or 128, times
> > instead.
>
> No! No! No.!
>
> Instead you should go read a book on the subject and choose
> a reasonable algorithm;
>
> For a 512-bit prime, 8 iterations of Miller-Rabin will suffice to
reduce
> the probability of a false positive to less than 2^-100. If one then
> follows with a SINGLE Lucas-Lehmer test, the chance of error
> becomes MUCH lower (although it has not been quantified exactly)
> Or one could use several round of the Frobenius-Grantham test.
>
> There are no known composites which get by a single M-R test
> followed by a single L-L test.
>
> >
> > --
> > ----------------------------------------------------------------
> > Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
> > Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
> > e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
> > WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
> >
>
> --
> Bob Silverman
> "You can lead a horse's ass to knowledge, but you can't make him
think"
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
--
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
http://www.ciphermax.com/book
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Truly random bistream
Date: Mon, 27 Dec 1999 18:23:10 +0000
Nigel Fitchard wrote:
> I would like to get hold of a truly random bitstream - about 2^24 bits long
> should be plenty. Does anyone know if such a thing exists for download ?
http://www.fourmilab.ch/hotbits/ uses radioactive decay.
http://www.random.org uses radio noise.
http://lavarand.sgi.com uses imaging of a Lava Lamp (tm).
At least one of them has archived formerly random bits to download.
The RAND Corporation's famous and hoary book "A Million Random Digits"
is on-line if archived random digits are suitable for your application.
The intro is at:
http://www.rand.org/publications/classics/randomdigits
and the digits themselves are at:
http://www.rand.org/publications/classics/randomdigits/randomdata.html
Since each of the million digits is worth a smidge over 3 bits, that might
just give you your 2^24 bits if you're careful.
--
Jim Gillogly
Mersday, 5 Afteryule S.R. 2000, 18:06
12.19.6.14.15, 4 Men 3 Kankin, Seventh Lord of Night
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: how good is RC4?
Date: Mon, 27 Dec 1999 18:49:12 GMT
Tom St Denis wrote:
> RC4 is not a trademark.
Um, sorry. You're mistaken. 3 minutes actually *looking* at the trademark database
shows it's a trademark of RSA.
http://trademarks.uspto.gov/cgi-bin/ifetch4?ENG+ALL+3+949707+0+0+370981+F+2+3+1+MS%2fRC4
> It's not a TM, and call it RC4. Rivest deserves respect.
He does, but it's still a trademark.
--
Darren New / Senior Software Architect / Dai Ye
San Diego, CA, USA (PST). Cryptokeys on demand.
Wenglish: "What's a sud?"
------------------------------
From: Greg <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto;
Subject: Re: Are PGP primes truly verifiable?
Date: Mon, 27 Dec 1999 18:49:28 GMT
Bob, I don't want to get into a shouting match.
> > With ECC, a private key is simply an integer (any value will do)
> > and the public key is always a valid result of a point multiply.
> > To be specific, ECC keys are all valid. Yet, PGP and other IFC
> > keys are getting to the point where verifying their validity
> > of strength is impossible.
>
> A rather bold assertion. Please back it up with some facts, please.
Correct me if I am wrong, but didn't you point out that if
p and q are made up of factors that are each about 100 or less
bits, then the attack is feasible? Is that not answering
my original question as, "yes, IFC cannot guarantee the level
of security it is advertised to provide"?
My point is that I do not see this or any similar issue
with ECC. That was my point all along.
--
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
http://www.ciphermax.com/book
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Craig Clapp" <[EMAIL PROTECTED]>
Subject: Why doesn't RSA use n=pqr ? (was Re: Are PGP primes truly verifiable?)
Date: Mon, 27 Dec 1999 19:09:26 GMT
If it takes about as much effort to factor a given size integer
having three roughly equal factors as it does to factor a similar
sized integer having just two roughly equal factors (in each case
using the best known factoring algorithm for the case in question),
can anyone explain the reason that it is not standard practice for
an RSA modulus to be the product of three primes, p, q, r, since this
would allow more efficient decryption than the two-prime case when
using the Chinese Remainder Theorem?
Using three factors instead of two appears to offer roughly a two-fold
speed improvement to decryption (taking the cost of a modular
exponentiation as log(p) ^ k with 2.5 ~< k ~< 3 ).
The small reduction in maximum order of an element ( LCM(p,q,r)
versus LCM(p,q) ) does not seem to be a severe drawback so long
as the factors are well chosen.
- Craig Clapp
Peter L. Montgomery wrote ...
>
> A better approximation is that the time to factor a product
>is independent of the factor sizes if the factors exceed
>the cube root of the product. This would apply to a 512-bit product
>with 200-bit and 312-bit prime factors (cube root has 171 bits),
>but not to a 512-bit product with several 2-bit (or 100-bit) prime factors.
>
> The major known algorithms for factoring hard numbers are ECM
>(elliptic curve method) and GNFS (general number field sieve).
>The largest factor found by ECM so far is a 53-digit prime factor
>of 2^677 - 1, by Conrad Curry. The largest GNFS factorization is
>RSA-155 (512 bits) by The Cabal. To a first approximation,
>the time ECM needs to find a factor depends upon the size of the factor,
>but the time taken by GNFS depends upon the size of the product.
>Huge amounts of machine time have
>been invested in both algorithms, although ECM probably gets more use
>since it is easier to program and needs little disk space.
>53 digits is about one third of 155 digits.
>Numerous factors over 40 digits have been found by ECM
>(but one is still proud to discover another).
>It is now routine to factor arbitrary 120-digit numbers by GNFS
>(but this may take a few CPU-months).
>I find it hard to predict whether we will get a 70-digit ECM factor
>before we factor a hard 200-digit digit number by GNFS.
>
>--
>E = m c^2. Einstein = Man of the Century. Why the squaring?
>
> [EMAIL PROTECTED] Home: San Rafael, California
> Microsoft Research and CWI
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Employing digits of pi
Date: Mon, 27 Dec 1999 20:16:00 +0100
The following is related to some stuff I posted quite a time back
but not discussed in this special setting as far as I can remember.
It is known that the digits of pi can be computed starting from
any arbitrarily chosen position. Let n indices giving such starting
positions be given. One obtains with these n subsequences of pi.
Now add the corresponding digits of the n subsequences modulo 10
(or the base, if this is not 10), resulting in a digit sequence
which we call R.
Questions: Can we do any inference on R? If yes, how does the
complexity of the task increase with n?
M. K. Shen
------------------------------
Reply-To: "modokon" <[EMAIL PROTECTED]>
From: "modokon" <[EMAIL PROTECTED]>
Subject: Q: Cryptanalysis Shareware?
Date: Mon, 27 Dec 1999 19:31:17 -0000
Hello,
Is there any share/free ware that will enable me to play
with encrypted messages (e.g. transposition etc). I'm
reading Simon Singh's "The Code Book" and would like to scan
it in & play a little without having to program in BASIC!
Thank for any pointers,
Joe
------------------------------
From: [EMAIL PROTECTED] (BigJim44)
Subject: PKZIP compression security
Date: 27 Dec 1999 19:34:51 GMT
I know it's not exactly PGP but would zipping a text file with PKZIP before
encipherment significantly increase the security of the link?
Thanx...
[EMAIL PROTECTED]
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: how good is RC4?
Date: Mon, 27 Dec 1999 19:48:58 GMT
In article <84691r$4cl$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> fungus <[EMAIL PROTECTED]> wrote:
> > RC4(tm) is really good, but has a couple of problems:
>
> RC4 is not a trademark.
>
> > 1) You can never use the same password twice unless you use salt
> > (*many* RC4 systems were stillborn because of this one).
>
> Any system should be still born without the usage of salts on
> passphrases or shared secrets...
>
> > 2) There are some weak password. This is easy to avoid by throwing
> > away the start of the output (the first 256 bytes is plenty).
>
> Good idea.
>
> > If you bear these two things in mind and code accordingly then you
> > should be as safe as with any other cipher.
>
> Any other cipher?
>
> > See: http://www.ciphersaber.gurus.com/ for examples.
>
> it's really simple, no need to read software... it's just
>
> init_key()
> {
> x = y = 0;
> for i = 0 to 255
> s[i] = i;
>
> for i = 0 to 255
> y = (y + key[i] + s[i]) mod 256
> tmp = s[y]; s[y] = s[i]; s[i] = tmp;
>
> <dump some>
> }
>
> get_rc4_byte()
> {
> x = (x + 1) mod 256;
> y = (s[x] + y) mod 256;
> tmp = s[x]; s[x] = s[y]; s[y] = tmp;
>
> return s[(s[x] + s[y]) mod 256];
> }
>
Is your post exporting strong encryption?
Perhaps I should ask are you in the United States of America?
--
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
http://www.ciphermax.com/book
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
