Cryptography-Digest Digest #760, Volume #10 Sat, 18 Dec 99 07:13:00 EST
Contents:
Re: discrete logorithm reduction to factoring (David Wagner)
Re: Prime series instead (Re: Pi) ("Douglas A. Gwyn")
Re: DES as pseudo random number generator ("Douglas A. Gwyn")
Re: The Code Book
Re: discrete logorithm reduction to factoring (David Wagner)
Re: DES key safety (Paul Rubin)
Re: More idiot "security problems" ("Douglas A. Gwyn")
Re: DES key safety (David Wagner)
Re: DES key safety (David Wagner)
Re: Prime series instead (Re: Pi) (Matthew Montchalin)
Re: Prime series instead (Re: Pi) (Matthew Montchalin)
Re: More idiot "security problems" (Johnny Bravo)
Re: More idiot "security problems" (Johnny Bravo)
Re: More idiot "security problems" (Johnny Bravo)
Re: DES key safety ("Douglas A. Gwyn")
Re: ARC4 cipher... >> is symmetric stream cipher with UNLIMITED key length (Johnny
Bravo)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: discrete logorithm reduction to factoring
Date: 17 Dec 1999 22:58:14 -0800
In article <83eoj0$a8$[EMAIL PROTECTED]>,
Bill Unruh <[EMAIL PROTECTED]> wrote:
> Thus an efficient discrete logs algorithm implies a probabilistically
> efficient factoring algorithm.
Be careful. This statement, while true if interpreted generously, is
likely to mislead many readers.
An efficient algorithm for discrete logs mod n implies an efficient
algorithm for factoring n.
But today's discrete log systems work mod p, a prime -- and an efficient
algorithm for discrete logs mod p implies NOTHING about factoring RSA
numbers like n. (So far as is known today, in the open literature.)
I could have sworn I explained this just a few days ago, here on sci.crypt.
I must not have done a very good job...
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Prime series instead (Re: Pi)
Date: Sat, 18 Dec 1999 07:00:45 GMT
Matthew Montchalin wrote:
> SDpikachu wrote:
> | Yes, but 1 isnt a prime,
> Unless we make it an honorary prime, like the 2 is an honorary prime.
2 is a genuine prime.
Whether or not 1 is considered a prime was determined by noting
that it was much more *useful* for it not to be so. Then the UFT
(for example) is much simpler to formulate.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES as pseudo random number generator
Date: Sat, 18 Dec 1999 07:01:36 GMT
Markus Eiber wrote:
> As you know one-time-pad is a cipher with perfect secrecy.
> How about a one-time-pad using a DES generated pseudo random number
> sequence?
You contradict yourself.
------------------------------
From: <[EMAIL PROTECTED]>
Subject: Re: The Code Book
Date: Sat, 18 Dec 1999 07:06:45 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Warner wrote:
>>
>> The first sentence of Simon Singh's _The Code Book_ is, "On the morning
>> of Wednesday, 15 October 1586, Queen Mary entered the crowded courtroom
>> of Fotheringhay Castle". The calendars I have referred to give this date
>> as being on a Saturday. I'm interested in hearing comments on this
>> apparent inconsistency or references to such.
> Are you sure that the calendars you referred to are using Julian dates?
> (Most of Europe changed to the Gregorian calendar in 1582; Britain waited
> until 1753, IIRC.)
> - --
> David Hopwood <[EMAIL PROTECTED]>
> PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
> RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
> "Attempts to control the use of encryption technology are wrong in principle,
> unworkable in practice, and damaging to the long-term economic value of the
> information networks." -- UK Labour Party pre-election policy document
> -----BEGIN PGP SIGNATURE-----
> Version: 2.6.3i
> Charset: noconv
> iQEVAwUBOFnE1TkCAxeYt5gVAQFdbggAp1bWm5/K4YeXCHCvsRaWAP/nBlWMws8w
> DIvr1L+00Qb83f2rP+UZ6Q8KDw+j8E1sxB8ZPTiSSk9Hxbj9DAzcg3/xGLP/2qsA
> 8zWr/8Whwoc5sNgZoPrc9SgNCI8dWG76fh8UcvyD3dV9keULA30VjBjzwaMaq2EK
> CFsiniZd+xwfQn2NPeILkQeqKX5wO2RTjI59G9hqjs9vHEes9hVTRy+UhNXla3mw
> ARKdmZTxXJXqpGTCiR49Mus7aR95GtaObFwxupZ4ybkgagB1VjujbPBwXj8/noox
> t+yBepbhx45eUl2SUk4JCd/2ZTE5WLc7vkbLwOl++TWAGYrez3JHaA==
> =XxFC
> -----END PGP SIGNATURE-----
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: discrete logorithm reduction to factoring
Date: 17 Dec 1999 23:10:48 -0800
In article <[EMAIL PROTECTED]>,
DJohn37050 <[EMAIL PROTECTED]> wrote:
> My understanding that is that if you can solve DL, you can also solve IF.
This is true in some sense, but false in a much more important sense, as I
have explained in other posts to this forum.
Consequently, it may be highly misleading if you rely on it when choosing
a public key cryptosystem. If you weren't careful, you might conclude from
the above that
~ if you can break today's discrete log cryptosystems you
will be able to break today's integer factoring cryptosystems. ~
Such a conclusion is NOT valid.
Today's discrete log cryptosystems (which work mod p, a prime) are believed
to be of roughly the same strength as today's integer factoring cryptosystems
(which work mod n, a composite of about the same size as p), but no proof is
known _in either direction_. The only reduction known is between discrete
logs mod n and factoring n, but today's discrete log systems don't work mod n.
(I'm sure D. Johnson understood this; I just wanted to warn the less
sophisticated reader of a pitfall here.)
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: DES key safety
Date: 18 Dec 1999 07:16:41 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>One question that would be nice to resolve is whether a single
>64-bit block of corresponding plain and ciphertext always
>determines a *unique* 56-bit DES key. (It's not obvious.)
This is something that Deep Crack could determine in a few days.
Why don't you suggest it to EFF? They've said that Deep Crack is
available for research projects and this seems like a reasonable one.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: More idiot "security problems"
Date: Sat, 18 Dec 1999 07:17:47 GMT
Eric Lee Green wrote:
> Unfortunately, it appears that a) people are stupid and will run
> anything that comes into their mailbox, ...
That's not necessarily due to stupidity -- sometimes the mail
interface automatically interprets HTML, for example, invoking
"helpers" for embedded file types etc. Most end users have no
idea that e-mail should be "plain", especially since they can't
see what their friends are e-mailing them when in that mode.
> and b) people care more about their own convenience than about
> security, thus commercial OS vendors similarly care ...
Most people buy computers to do certain things, such as access
Web sites, use e-mail, play games, prepare correspondence, etc.
Virtually nobody buys a computer "to be secure". Therefore,
bells & whistles are selling points and security is not. The
demand for security normally comes only after there has been an
incident that affects the user personally, which is of course
too late.
I think the only hope is to migrate to distributed computing,
*building in* security at the lowest levels of protocol, as
has been done in Plan 9 and Kerberos for example. That way,
at least *some* of the system remains secure even if somebody
screws up at a higher level.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: DES key safety
Date: 17 Dec 1999 23:18:35 -0800
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> [ known-plaintext attacks on DES ]
>
> Actually that is not known. My last-year's research project was
> precisely on general methods for doing such things, and I didn't
> determine that it was hopeless. (The project was abandoned due
> to lack of funding.) The basic approach was along the lines that
> Keith Muller and I worked out many years ago; essentially, you
> solve the simultaneous encryption equations; it's a big system,
> but easily respresentable within a modern computer's RAM.
> Various methods are available for performing efficient reductions.
Hasn't that been tried before, maybe two decades ago, with resounding
lack of success?
Has anything fundamental changed since then that might cause us to
re-evaluate the chances of success of such an approach?
Or is this a case of looking at it with a fresh mindset and hoping to
see something new? (certainly a time-proven approach. I'm not trying
to denigrate the research project; I'm just curious if there have been
any relevant advances in solving non-linear systems of equations or
somesuch other change that already invalidates the tentative conclusions
from many years ago and makes such an approach look more promising now
than it did then, or whether this is just new work on a long-standing
open problem)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: DES key safety
Date: 17 Dec 1999 23:35:23 -0800
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> One question that would be nice to resolve is whether a single
> 64-bit block of corresponding plain and ciphertext always
> determines a *unique* 56-bit DES key. (It's not obvious.)
Yes. Non-obvious indeed.
However, it would be extremely surprising if the answer is `yes'.
Here's a counting argument which suggests that the answer should be
`no', for a random cipher. Fix any 64-bit plaintext and ciphertext,
and let X be a random variable that counts the number of 56-bit DES keys
that encrypt the plaintext block to the ciphertext block. We have
Pr[X=0] = (1 - 2^{-64})^{2^{56}}
~ exp{-1/256} ~ 1 - 1/256, and
Pr[X=1] = 2^{56} * 2^{-64} * (1 - 2^{-64})^{2^{56} - 1}
~ exp{-1/256} / 256 ~ 1/256 - 1/65536.
Consequently, Pr[X>1] = 1 - Pr[X=0] - Pr[X=1] ~ 1/65536.
So, for any fixed plaintext/ciphertext pair, we have about a 1/2^16 chance
that the DES key fails to be uniquely determined. This is quite low.
But there are 2^{128} different plaintext/ciphertext pairs in all.
Therefore, we should expect (for a random cipher) that many of those
will fail to uniquely determine a DES key, and indeed, with extremely
high probability, there will be at least one which shows that the answer
to your question is `no' for this cipher.
Of course, this proves nothing about DES, because DES is not a random
cipher. But, as a heuristic, I think it shows that it would be a
surprising and extremely interesting property of DES, if it were true
that a single 64-bit block of corresponding plain and ciphertext *always*
determines a unique 56-bit DES key.
Another interesting feature of this calculation is that it suggests
we could find a proof that the answer is `no' (as expected) using just
2^{72} work or so, if indeed it is true that (as is widely believed) DES
behaves like a random cipher. We simply pick a random 64-bit plaintext
and ciphertext pair and run the EFF DES cracker on it to see if two
keys are found; repeat until a proof is found, noting that we expect
to succeed after about 2^16 tries if DES acts like a random cipher.
(In practice, the workfactor could be reduced by a factor of 256, if one
is willing to adopt slightly more heuristic assumptions -- we merely
pick a random 64-bit plaintext and a random 56-bit key K, encrypt to
obtain a 64-bit ciphertext, and run the DES cracker to check if there
is a key K' != K that also yields the same plaintext/ciphertext pair;
repeating 256 times should suffice, if DES behaves like a random cipher.)
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Prime series instead (Re: Pi)
Date: Sat, 18 Dec 1999 01:39:08 -0800
On Sat, 18 Dec 1999, Douglas A. Gwyn wrote:
| Matthew Montchalin wrote:
| > SDpikachu wrote:
| > | Yes, but 1 isnt a prime,
| > Unless we make it an honorary prime, like the 2 is an honorary prime.
|
| 2 is a genuine prime.
|
| Whether or not 1 is considered a prime was determined by noting
| that it was much more *useful* for it not to be so. Then the UFT
| (for example) is much simpler to formulate.
Fine. Add it in after everything else is figured out. Does the resulting
number have any practical use?
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Prime series instead (Re: Pi)
Date: Sat, 18 Dec 1999 01:49:05 -0800
On Sat, 18 Dec 1999, Douglas A. Gwyn wrote:
| Matthew Montchalin wrote:
| > SDpikachu wrote:
| > | Yes, but 1 isnt a prime,
| > Unless we make it an honorary prime, like the 2 is an honorary prime.
|
| 2 is a genuine prime.
|
| Whether or not 1 is considered a prime was determined by noting
| that it was much more *useful* for it not to be so. Then the UFT
| (for example) is much simpler to formulate.
Okay. We could talk about the set of odd primes, then, if we wish to
leave out 2. It is just that most people look at most primes, and jump to
the conclusion that bit 0 is set. It makes it a lot easier to deal with
writing code to play with primes....
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: More idiot "security problems"
Date: Sat, 18 Dec 1999 05:40:21 GMT
On 17 Dec 1999 19:24:47 GMT, [EMAIL PROTECTED] (Xcott Craver)
wrote:
> Well-spotted! Now, can we think of a character who embodies
> all four properties? I've always wanted a good term for
> coders who reinvent square wheels. How about ... well, I've
> exhausted most of today's creative juices. There's got to
> be a million sitcoms where someone gets instant-expert syndrome
> about something he doesn't understand and accidentally creates
> a plotline. Who does that a lot?
Homer Simpson.
Best Wishes,
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: More idiot "security problems"
Date: Sat, 18 Dec 1999 05:46:40 GMT
On 17 Dec 1999 19:05:14 GMT, [EMAIL PROTECTED] (JPeschel)
wrote:
>You'll find most commercial encryption programs, including PGP, do some
>sort of check for a correct password during decryption. Is this what you
>mean by "having a decryption key buried in the code?"
No, in PGP the decryption key is not in the code, you type it in
yourself. There are programs that encrypt your data with a password
that the program knows internally, these are trivial to find, so a
copy of the encrypted data is barely more secure than plain text.
>Stepping through and editing snippets of code, or applying a patch, won't
>work if the the password checking algorithm, usually a one-way hash,
>is secure.
>
>Joe
The listed case was the password is in the program (like storing
your mail login password so you don't have to type it in every time),
trivial work to go in the program and find how it encrypts your
password for storage. Then you just write another program to decrypt
the encrypted password, it might as well be plain text if you can get
a copy of the stored encrypted password.
Best Wishes,
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: More idiot "security problems"
Date: Sat, 18 Dec 1999 05:49:34 GMT
On 17 Dec 1999 20:03:45 GMT, [EMAIL PROTECTED] (JPeschel)
wrote:
>Green, however, gave me the impression that he could debug and
>reverse or patch any encryption program that checked for a correct
>password. I contend it's not always possible.
>
>Joe
Not all programs, just programs that store encrypted data with an
internal password rather than a user supplied one. (The example was a
program that stored your email login so you didn't have to type it in
every time.) His point was that any data stored by such a program
would be poorly protected as it would be easy to reverse the
encryption on the stored login to recover it.
Best Wishes,
Johnny Bravo
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES key safety
Date: Sat, 18 Dec 1999 10:54:14 GMT
David Wagner wrote:
> Hasn't that been tried before, maybe two decades ago, with resounding
> lack of success?
Hard to say for sure, since negative results tend not to get published.
Anyway, I never heard that it had been tried by anyone who had a clue.
It is very much a computer science project as opposed to a mathematical
project; instead of actually constructing the full set of equations in
canonical form and then plugging in the known values, the known values
can be plugged in first and used while the DES "program" is "executed".
With reductions applied throughout the process, including if necessary
searches over relatively small spaces, there seems to be a good chance
that the problem can be kept manageable.
Note that the nonlinearity is not very scary, since we're dealing
with GF(2) here. GF(2) has lots of *very* nice algebraic properties.
There has been previous work in a general context by the people who
design Boolean logic circuits (CPUs, etc.) - Karnaugh maps and all
that. So obviously progress can be made; the question is how far.
It's also evident that if such an approach works for DES, it would
work for very many other popular block ciphers.
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: ARC4 cipher... >> is symmetric stream cipher with UNLIMITED key length
Date: Sat, 18 Dec 1999 06:43:30 GMT
On Sat, 18 Dec 1999 00:09:38 -0500, [EMAIL PROTECTED] wrote:
>The RC4 is symmetric stream cipher with unlimited key length >> UNLIMITED
The key length is limited to 2048 bits, and only with the
restriction that you never use the same key twice. 2048 is bit, but
not unlimited.
If you want to reuse keys with a 10 byte IV you are limited to 1968
bits. To avoid a known class of weak keys you should take off another
bit (roughly speaking).
You have to change the design of RC4 to use keys greater than 55
bytes or so (add multiple rounds to the key mixing function to ensure
the IV is properly mixed with the key), the effect of multiple mixing
rounds may introduce a weakness.
I know that analysis has shown that one round mixing with large keys
is very poor security for multiple messages as the chance of the IV
not mixing with any particular byte gets pretty high. Letting the
attacker compare multiple texts and stand a good chance of extracting
the key. I don't know if the multiple mixing variant has received any
extensive analysis but from the limited analysis I have seen it looks
to be effective.
>Very common realizations are using key lengths of up to 2048 bits.
That is because the key can only have 256 elements with 8 bits each.
Going beyond this would require a complete redesign of the entire
system, and it would no longer be RC4. For 2048 bits though, you have
to use a different key for every message, but for many implementations
this is not a problem. But if you can set this much up ahead of time,
you may as well use a OTP. :)
>The key length of 128 bits in symmetric ciphers is considered to be very
>secure, you can see what increase of the key length to 2048 bits can provide for you.
Anything higher than 256 bits is pure overkill given that any
encryption can decrypt to just about every possible plaintext of the
same length. And to get that high you need to stop using English Text
as keys, you can reasonably expect to reach about 150 bits of key in
55 bytes of English Text chosen at random from a word list (like
DiceWare). At this point you are probably going to need physical
security for your keys, as you won't be able to memorize them anymore.
With multiple mixing rounds, or never reusing a key, you can get up
to about 600 bits of key for English Text but who wants to memorize a
46 word passphrase. :)
>USA Gov. permitted in the past implementations outside US to be of max 40 bits
>key length, which is child play to break for any federal agency.
Child's play for civilians as well. A 40 bit DES System would last
less than 1 minute on the EFF cracker. :)
Best Wishes,
Johnny Bravo
------------------------------
** 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
******************************
