Cryptography-Digest Digest #785
Cryptography-Digest Digest #785, Volume #9 Sun, 27 Jun 99 02:13:04 EDT Contents: Re: A few questions on RSA (Gilad Maayan) Re: determining number of attempts required (S.T.L.) Re: Moores Law (a bit off topic) (david avery) Re: A few questions on RSA (S.T.L.) Re: DES-NULL attack (wtshaw) Re: A few questions on RSA (David A Molnar) Re: determining number of attempts required (JPeschel) From: [EMAIL PROTECTED] (Gilad Maayan) Subject: Re: A few questions on RSA Date: Sun, 27 Jun 1999 03:54:26 GMT Take the following encryption scenario: A 20 bit cyphertext is encrypted into a 20 bit cyphertext using a 1024 bit RTS pubic key. The public exponent is only about 100 bits long; the secret exponent would be around 900 (if I'm not mistaken). Anyhow, we're talking about a drastically small public key, and a correspondingly large secret key. I'm assuming, in the above scenario, that all of the following are true. Please note that I'm making a somewhat unconventional use of RTS - I know moduluses are usually kept in the public domain, etc. 1. An attacker knowing neither the modulus nor the public key, but knowing the exact length of the plaintext, would not be able to extrapolate the key from the cyphertext. 2. Let's assume the attacker knows the plaintext but not the modulus or the public key. The key space is indeed small in this case - only 2^20 - but this only means that each 20-bit combination would have an enormous amount of 'possible' 512/1024 keys (keys that, when used on the plaintext, would encrypt it as the known cyphertext). Therefore, you could test the entire keyspace (only about 1.05 million keys) to find a key that works, but you would have no way in hell of knowing which key was actually used. 3. Let's assume the attacker knows the plaintext, the cyphertext, the modulus, and the secret key (not the public key). For the reasons stated above, even though the effective key space is only 2^20, he would have to actually break 1024-bit RTS to know the key that was used in encryption - simply testing each one of the million-odd possible combinations would not yield the key. Furthermore, in our specific scenario, it would make no difference to an attacker that the public exponent was unusually small - 1024 RTS would be just as hard to break. I'd like to hear your comments on this. Also, I have another question, which appeared in the original message but wasn't answered to my satistfaction: Let's say you encrypt a message with triple DES, using two keys extrapolated from a key-seed by a function. You send the cyphered message together with the key-seed, without encrypting the key-seed in any way. If the functions are unknown to an attacker (forget the key-management issues), would it be able to extrapolate them from the key-seed and cyphertext? Many thanks, Gilad Maayan -- From: [EMAIL PROTECTED] (S.T.L.) Subject: Re: determining number of attempts required Date: 27 Jun 1999 04:42:01 GMT The password picked (by me, if you must know) was designed specifically to resist attacks :) I see several scenarios, increasingly interesting. I'd like to know which (if any!) are the case, actually. 1) You've encoded something important and have forgotten the exact key. However, certain details you stated about how fast you can try keys makes me think that the files are on some other computer, which you can't access. 2) You've given someone else guidelines to create a password (very, very unusual guidelines), and are now trying to crack it. Unlikely. 3) You picked a password to encode information, but have forgotten its exact contents AND are no longer allowed actual access to the encrypted data. This is the most interesting one. I'm getting really curious as to what you're trying to crack open! :-D -*---*--- S.T.L. === [EMAIL PROTECTED] === BLOCK RELEASED!2^3021377 - 1 is PRIME! Quotations: http://quote.cjb.net Main website: http://137.tsx.orgMOO! "Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8 E-mail block is gone. It will return if I'm bombed again. I don't care, it's an easy fix. Address is correct as is. The courtesy of giving correct E-mail addresses makes up for having to delete junk which gets through anyway. Join the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my .sig is shorter and contains 3379 bits of entropy up to the next line's end: -*---*--- Card-holding member of the Dark Legion of Cantorians, the Great SRian Conspiracy, the Triple-Sigma Club, and the Union of Quantum Mechanics Avid watcher of "World's Most Terrifying Causality Violations", "World's Scariest Warp Accidents", and "When Tidal Forces Attack: Caught on Tape" Patiently awaiting the launch of Gravity Probe B and the discovery of M39 Physics Commandment #2: Thou Shalt Conserve Mass/Energy In Closed Systems.
Cryptography-Digest Digest #786
Cryptography-Digest Digest #786, Volume #9 Sun, 27 Jun 99 12:13:03 EDT Contents: Re: A few questions on RSA (S.T.L.) Re: On an old topic of internet publication of strong crypto (Bill Unruh) Re: On an old topic of internet publication of strong crypto (JPeschel) Re: A few questions on RSA (David A Molnar) Re: determining number of attempts required (JPeschel) Re: DES-NULL attack (Thomas Pornin) Re: Moores Law (a bit off topic) (Thomas Pornin) Re: DES-NULL attack (Rob Warnock) Re: Moore's Trend ([EMAIL PROTECTED]) Re: Converting arbitrary bit sequences into plain English texts ([EMAIL PROTECTED]) Re: Moore's Trend (fungus) Des keys ([EMAIL PROTECTED]) Re: Tough crypt question: how to break ATT's monopoly??? (fungus) Re: Tough crypt question: how to break ATT's monopoly??? (fungus) Re: Kryptos article (Lincoln Yeoh) Re: Des keys (fungus) Re: Des keys (Thomas Pornin) Re: Kryptos article (Lincoln Yeoh) Re: Tough crypt question: how to break ATT's monopoly??? (Dave Hazelwood) Re: A few questions on RSA (DJohn37050) New version of free disk encryption product for NT (with Scramdisk support) ([EMAIL PROTECTED]) --- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein) From: [EMAIL PROTECTED] (S.T.L.) Subject: Re: A few questions on RSA Date: 27 Jun 1999 06:34:33 GMT There are attacks for small public keys, but there small = "e = 3". Really? How do they work? -*---*--- S.T.L. === [EMAIL PROTECTED] === BLOCK RELEASED!2^3021377 - 1 is PRIME! Quotations: http://quote.cjb.net Main website: http://137.tsx.orgMOO! "Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8 E-mail block is gone. It will return if I'm bombed again. I don't care, it's an easy fix. Address is correct as is. The courtesy of giving correct E-mail addresses makes up for having to delete junk which gets through anyway. Join the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my .sig is shorter and contains 3379 bits of entropy up to the next line's end: -*---*--- Card-holding member of the Dark Legion of Cantorians, the Great SRian Conspiracy, the Triple-Sigma Club, and the Union of Quantum Mechanics Avid watcher of "World's Most Terrifying Causality Violations", "World's Scariest Warp Accidents", and "When Tidal Forces Attack: Caught on Tape" Patiently awaiting the launch of Gravity Probe B and the discovery of M39 Physics Commandment #2: Thou Shalt Conserve Mass/Energy In Closed Systems. -- From: [EMAIL PROTECTED] (Bill Unruh) Subject: Re: On an old topic of internet publication of strong crypto Date: 27 Jun 1999 06:33:04 GMT In [EMAIL PROTECTED] [EMAIL PROTECTED] (JPeschel) writes: That's not what he said. A scientific paper is not subject to export restriction. This is true if it is on paper. However if it is posted on the net, and it contains crypto source code then it is export restricted. This is precisely the heart of the Bernstein case. -- From: [EMAIL PROTECTED] (JPeschel) Subject: Re: On an old topic of internet publication of strong crypto Date: 27 Jun 1999 06:54:08 GMT [EMAIL PROTECTED] (Bill Unruh) writes: That's not what he said. A scientific paper is not subject to export restriction. This is true if it is on paper. However if it is posted on the net, and it contains crypto source code then it is export restricted. This is precisely the heart of the Bernstein case. Yeah, Bill, you're right, the paper cannot contain source code and be posted on the net. I thought I made the distinction between source code and scientific paper clear. I guess not. It seemed obvious to me that a scientific paper, in electronic form, that contained source would be export restricted. Joe __ Joe Peschel D.O.E. SysWorks http://members.aol.com/jpeschel/index.htm __ -- From: David A Molnar [EMAIL PROTECTED] Subject: Re: A few questions on RSA Date: 27 Jun 1999 07:22:03 GMT S.T.L. [EMAIL PROTECTED] wrote: There are attacks for small public keys, but there small = "e = 3". Really? How do they work? Very vaguely : by using several related ciphertexts to develop a system of simultaneous equations, then finding equivalent equations which can be solved over the integers with the same solutions. Since it is easy to solve equations like x^y = c over the integers, this breaks the system and recovers the message in question. Alternative vague formulation : construct a lattice from a system of simultaneous equations based on some ciphertexts. Show that the vectors in this lattice are unique within a ball of exponential radius. i Fix it so the shortest vector in the lattice corresponds to the plaintext you want.
Cryptography-Digest Digest #787
Cryptography-Digest Digest #787, Volume #9 Sun, 27 Jun 99 15:13:02 EDT
Contents:
The One-Time Pad Paradox
Re: Tough crypt question: how to break ATT's monopoly??? ([EMAIL PROTECTED])
Re: one time pad ([EMAIL PROTECTED])
Re: Kryptos article ("Douglas A. Gwyn")
Re: one time pad ([EMAIL PROTECTED])
Re: Converting arbitrary bit sequences into plain English texts (wtshaw)
Re: one time pad ([EMAIL PROTECTED])
Re: DES-NULL attack ([EMAIL PROTECTED])
Re: DES-NULL attack ([EMAIL PROTECTED])
Re: Kryptos article (wtshaw)
Re: DES-NULL attack ([EMAIL PROTECTED])
Re: A few questions on RSA (Gilad Maayan)
Re: The One-Time Pad Paradox (S.T.L.)
From: [EMAIL PROTECTED] ()
Subject: The One-Time Pad Paradox
Date: 27 Jun 99 15:39:19 GMT
The One-Time Pad is the one theoretically perfect cipher. Provided it is
applied in strict accordance with the theoretical conditions.
One must use a key that is truly and genuinely random.
Now, there is a small, but finite, probability that the random key will
happen to be 00...
If one uses such a key, one is sending one's message in plaintext.
If one refuses to use such a key, one is causing one's key to be
nonrandom, hence one is spoiling the perfection of the one-time-pad.
This qualifies as a genuine paradox, and as such may well be fruitful,
just as paradoxes in mathematics and physics have occasionally led to new
paradigms.
One way to resolve the "next step" after this paradox: let us suppose
one's key *does* look random, but applying the key to the message creates
what _appears_ to be the plaintext of a message saying (in different
words) essentially the same thing as the message you want to keep
secret...
is the following: before applying the OTP, encrypt one's message with a
probabilistic encryption method. If this happens, repeat the probabilistic
encryption, and use the same OTP again, _then_ send the result.
Since the pad is random, the only "information" is that the _ciphertext_
is random-looking, and one already has the full ciphertext.
However, that *does* introduce a subliminal channel...
(I call this Comfort-Zone Encryption.)
The desired situation to avoid this paradox is this: you have N plaintext
messages, you have N keys, and you have N ciphertext messages. But no one
of the N keys is "zero", and *none* of the N ciphertext messages could be
mistaken (by someone who doesn't realize a one-time-pad is being used) for
any plaintext - or could be thought to be more closely associated with one
plaintext message than another.
Stating the condition helps to see what is necessary. A step (but an
incomplete one) would be to take an alphabetic text, and by means of a
random key encipher it to a ciphertext consisting of 26 funny-looking
symbols instead of the 26 letters, which occasionally can have meaning
associated with them.
Surely there is, in mathematics, some class of equi-spaced binary strings
applicable to this kind of thing...
John Savard
--
From: [EMAIL PROTECTED]
Subject: Re: Tough crypt question: how to break ATT's monopoly???
Date: Sun, 27 Jun 1999 16:05:56 GMT
snip
With the PKZIP skeme you don't need much chosen /known plaintext
though. The only things it may be good for is highly compressed files
such as MP3 or JPG. In which case why are you zipping them?
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
--
Date: Sun, 27 Jun 1999 01:27:51 -0400
From: [EMAIL PROTECTED]
Subject: Re: one time pad
AllanW wrote:
[EMAIL PROTECTED] (S.T.L.) wrote:
This thread is disgusting. Most involving OTPs get ugly, but
*so* many kooks posting here have the wrong ideas.
Gosh, S.T.L., it's a good thing you're here to help us
distinguish the kooks from, say, the insufferable
egotistical asshole bastards.
I'll just state it plainly:
If you have a perfect random number generator
Is there such a thing? If so, how do you know?
that is operating correctly, then ALL you need to do is
take its output, send it to the recipient securely, and
How?
Doesn't the existance of a secure channel imply that no
encryption is needed?
No. This issue may belong in the FAQ. The secure channel may have
timing characteristics that make it unacceptable for real-time
communication, but acceptable for keypad communication. Condsider a
ship. At dock you can very easily transfer arbitrary amounts of pad
quite cheaply, and with almost total security. At sea, however, you
have no secure channel. I.e., it is intermittent, but the channel
capacity is unreasonably high.
If your ship is an SSBN and you want to send "DEFCON I", the OTP might
be useful.
--
From: "Douglas A. Gwyn" [EMAIL PROTECTED]
Subject: Re: Kryptos article
Date: Sat, 26 Jun 1999 03:49:50 GMT
Jim Gillogly wrote:
Reflecting on this, I realized it's
Cryptography-Digest Digest #788
Cryptography-Digest Digest #788, Volume #9 Sun, 27 Jun 99 19:13:03 EDT
Contents:
Re: one time pad (S.T.L.)
Re: Des keys (Jim Gillogly)
Re: The One-Time Pad Paradox (John Savard)
Re: one time pad (David A Molnar)
Re: A few questions on RSA (David A Molnar)
Re: Moores Law (a bit off topic) (John Savard)
Re: Moore's Trend (John Savard)
Re: VIC cipher now described on web site (John Savard)
Re: Tough crypt question: how to break ATT's monopoly??? ([EMAIL PROTECTED])
Re: The One-Time Pad Paradox ([EMAIL PROTECTED])
Re: DES-NULL attack ([EMAIL PROTECTED])
Re: Tough crypt question: how to break ATT's monopoly??? (Bill Unruh)
Hamming Weight ([EMAIL PROTECTED])
Re: New version of free disk encryption product for NT (with Scramdisk support)
([EMAIL PROTECTED])
Re: The One-Time Pad Paradox ("Robert C. Paulsen, Jr.")
Re: OTP is it really ugly to use or not? ([EMAIL PROTECTED])
Re: one time pad (Jerry Coffin)
Re: A few questions on RSA encryption (Jerry Coffin)
Re: Bytes of "truly random" data for PRNG seed. ([EMAIL PROTECTED])
Re: Hamming Weight (Tom Knight)
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: one time pad
Date: 27 Jun 1999 19:26:22 GMT
If your ship is an SSBN and you want to send "DEFCON I", the OTP might
be useful.
I don't argue with that, but the plain vanilla method is not useful if you want
to hide the very existence of the message. Imagine that Charlie is everywhere,
and one day he hears a very powerful radio signal with 64 bits contained in it
broadcast to every American submarine in the world. I don't know about you, but
if I were Charlie I would suspect that something big is about to go down.
However, if American Headquarters *regularly* broadcasts "ALL = OK" (using up
64 bits of the submarines' OTP pads every time they do that), Charlie will see
a regular broadcast of gibberish. The time that "DEFCON I" is broadcast will
then look no different to Charlie. Of course, OTP pad synchrony actually seems
to be highly important here.
-*---*---
S.T.L. === [EMAIL PROTECTED] === BLOCK RELEASED!2^3021377 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.orgMOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*---
Card-holding member of the Dark Legion of Cantorians, the Great SRian
Conspiracy, the Triple-Sigma Club, and the Union of Quantum Mechanics
Avid watcher of "World's Most Terrifying Causality Violations", "World's
Scariest Warp Accidents", and "When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #3: Thou Shalt Conserve Baryon Number.
--
From: Jim Gillogly [EMAIL PROTECTED]
Subject: Re: Des keys
Date: Sun, 27 Jun 1999 12:48:06 -0700
fungus wrote:
[EMAIL PROTECTED] wrote:
Just wondering... With a better key schedule and longer key DES could
have been slightly more secure (i.e probably ok for another 10 years).
Tne NSA wanted to be able to crack it in the '70s, remember...
An NSA guy at one of the Santa Barbara Crypto meetings told me (not
off-the record or classified or anything) that their horizon was
about 15 years: that they were willing to take the risk of putting
out an algorithm that they wouldn't be able to read if it were turned
against them for that long. This (he said) was the planning factor
both for DES and SKIPJACK. The 80-bit SKIPJACK cipher was supposed
to give them about the same blackout period if it were leaked, which
would put its safe life expectancy at around 2008, counting from
the Clipper I roll-out. This is a more aggressive development cycle
than envisioned by the SKIPJACK Committee, which estimated 30 years
beyond DES based (apparently) on Moore's uh, uh, ueber-den-Daumen
WAG of 18 months per binary order of magnitude.
I don't have an independent assessment of his credibility, but
he told me this with a straight face and I am quite sure that
if it were a real policy he would be in a position to know
about it. It is a priori credible that they'd be willing to
accept some period of illegibility, because the NSA has two
missions that are in some conflict: one is to read everybody
else's mail, and the other is to protect US communications.
It's a tough balancing act.
--
Jim Gillogly
Hevensday, 4 Afterlithe S.R. 1999, 19:30
12.19.6.5.12, 3 Eb 20 Zotz, Fourth Lord of Night
--
From: [EMAIL PROTECTED] (John Savard)
