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 <> 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. -- From: [EMAIL PROTECTED] (david avery) Subject: Re: Moores Law (a bit off topic
Cryptography-Digest Digest #784
Cryptography-Digest Digest #784, Volume #9 Sun, 27 Jun 99 00:13:03 EDT Contents: Re: A few questions on RSA encryption (S.T.L.) Re: trapdoor one way functions ([EMAIL PROTECTED]) Re: DES-NULL attack (Jerry Coffin) Re: determining number of attempts required ([EMAIL PROTECTED]) Re: A few questions on RSA encryption ([EMAIL PROTECTED]) Re: determining number of attempts required ([EMAIL PROTECTED]) Re: A few questions on RSA encryption (S.T.L.) Re: On an old topic of internet publication of strong crypto (JPeschel) Re: Moore's Trend (Horst Ossifrage) Re: A few questions on RSA encryption (Gilad Maayan) Re: VIC cipher now described on web site (Uri Blumenthal) From: [EMAIL PROTECTED] (S.T.L.) Subject: Re: A few questions on RSA encryption Date: 27 Jun 1999 01:13:43 GMT I'm replying to multiple posters, just to let you know. <> What kind of hardware limitations? That must be pretty limited - I can have a calculator (TI-89) that fits in my pocket (or a TI-92 if I have slightly larger pockets... :-D ) perform RSA with a 300-decimal-digit key, approximately a 1024-bit keysize! Of course, it's not *that* speedy. I said: <> Someone replied: <> By what I said, I was referring to how difficult it is for the Adversary to determine the *munged* keyseed used in the symmetric encryption, based on the ciphertext. The Adversary knows the non-munged keyseed, the symmetric algorithm, and the ciphertext. Apparently (according to the original poster), the Adversary does not have the plaintext. However, what the original poster IS concerned about is the security of the munging process, not the plaintext itself. That's a little odd, of course. When I referred to how well the symmetric cipher "hides" (see the quotation marks?) the *munged* keyseed, I meant exactly what I stated in the first sentence of the paragraph. The Adversary must FIRST determine the *munged* keyseed (which he does not know) from the symmetric encryption algorithm and the ciphertext, BEFORE comparing the *munged* keyseed with the keyseed he already knows, IN ORDER to determine the munging process, which is what the original poster is concerned about. Or maybe I'm wrong - the last question was quite complex and not a very common one. <> Why not? A little experiment: We have two friends: Al and Bob. They each can do RSA. Al prepares a modulus, and a secret key for himself and the corresponding public key. He gives the modulus and the public key to Bob, *securely*, just like he would give Bob an IDEA key securely. Bob does the same for Al. Now, Ezekiel enters the room, and prevents any secure communication (but does not, of course, compromise the security of their individual computers). Al and Bob can, however, send messages encrypted with RSA, and Ezekiel has no idea what the modulus is. Now, OBVIOUSLY, keeping the public key and modulus a secret prevents transmission of RSA keypairs over non-secure lines, making RSA effectively just like a symmetric cipher. But stronger, I say, because of it. :-D Of course, this would be unsuitable for an application like PGP, which lets users fully enjoy the advantages of asymmetric cryptography. <> I said extremely difficult, and then I said I could not *quantify* it. What is your problem with that? 512 bits seems "extremely difficult" to me. I never said "extremely difficult but feasible", which is what you interpreted it as. <> Um, duh. That's why no one really worries about chosen-plaintext attacks as long as the message is not extraordinarily small. That's why RSA is considered secure. You keep thinking I mean that these attacks are practical, which they (in general use) most certainly are NOT. <> Of course. But keeping the modulus secret improves security somewhat, with the associated disadvantages of more difficult use. Why reveal anything that you don't *have* to, if your algorithm is good? (Attention: NOT an argument for keeping algorithms secret, you see.) -*---*--- 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 awaiti
Cryptography-Digest Digest #783
Cryptography-Digest Digest #783, Volume #9 Sat, 26 Jun 99 21:13:03 EDT Contents: Re: RSA msg length... (Gilad Maayan) Re: A few questions on RSA encryption (Gilad Maayan) Re: A few questions on RSA encryption ([EMAIL PROTECTED]) Re: Kryptos article (Jim Gillogly) Re: Moores Law (a bit off topic) ([EMAIL PROTECTED]) trapdoor one way functions ([EMAIL PROTECTED]) Re: Tough crypt question: how to break AT&T's monopoly??? ([EMAIL PROTECTED]) Re: DES-NULL attack ([EMAIL PROTECTED]) determining number of attempts required (Keith A Monahan) Re: DES-NULL attack (JPeschel) Re: A few questions on RSA encryption ([EMAIL PROTECTED]) Re: determining number of attempts required ([EMAIL PROTECTED]) Re: A few questions on RSA encryption ([EMAIL PROTECTED]) Re: determining number of attempts required (Keith A Monahan) Re: RSA msg length... ([EMAIL PROTECTED]) Re: DES-NULL attack ([EMAIL PROTECTED]) From: [EMAIL PROTECTED] (Gilad Maayan) Subject: Re: RSA msg length... Date: Sat, 26 Jun 1999 21:18:19 GMT Okay, but what happens if the message is much smaller than the key? Say I'm trying to encrypt 20 bits with a 512 or 1024-bit key. Would I be able to? -- From: [EMAIL PROTECTED] (Gilad Maayan) Subject: Re: A few questions on RSA encryption Date: Sat, 26 Jun 1999 21:49:27 GMT >Okay, why involve RSA? If you are assuming that the Adversary has broken it, >why not *simplify* your scenario and have the keyseed sent in the clear? (We >can have absurd situations!) Well, for reasons of hardware limitations, I'm thinking of using a relatively small RSA key. So it will be a bit difficult for your casual attacker to break it, but a more determined analyser might get through it, and find this second layer. >Therefore, the strength of your resulting encryption... how well the symmetric cipher >"hides" the munged keyseed. Hold on, the symmetric cypher isn't hiding the keyseed - the keyseed is out in the open (in plaintext form). If it wasn't, you wouldn't be able to decrypt the message, and it would be pretty much useless. If I'm not mistaken. -- From: [EMAIL PROTECTED] Subject: Re: A few questions on RSA encryption Date: Sat, 26 Jun 1999 22:16:21 GMT In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Gilad Maayan) wrote: > 1. I haven't been able to find any information on the relationship > between the number of bits encrypted by RSA, and the level of security > obtained. Let's say you're encrypting 20 bits with a 512 or 1024 bit > key. Is the small size of the plaintext relevant? Will the encrypted > message be easier to crack than, say, an entire document encoded by > the same RSA key? Well I think PKCS #1 covers this and it should be <= half the modulus size if I am correct. I am not sure why you would have to read the standard. AC covers it as well. Also the size of the private exponent/modulus will effect the safety of the key. A smaller exponent/modulus will be easier to factor and thus find the private key. > 2. Would it be at all possible to break an RSA cyphertext, knowing > neither the secret key, the public key, or the modulus? If you know the secret exponent and the modulus (the modulus is public) then one could decrypt the ciphertext easily. > 3. Would it be possible to extrapolate an RSA key from a cyphertext, > if the plaintext was known? (assuming that neither the key used for > encryption nor its corresponding modulus are known). The plaintext is always known for the attacker. That's because the keys are public/private. So I would assume the answer is no. > 4. If the modulus and public key were known, would available > cyphertext-plaintext make the cryptoanalysis process faster or easier? The modulus is always known. The factors are not however. I don't think you understand the algorithm to well. I don't know the theory but I do know how it works. You have p and q which are prime. The modulus n = pq is public but p and q are not. e is the private exponent C = P^e mod pq, and the d is the public exponent P = C^d mod pq. Basically (pq, d) = public, (p, q, e) = private. You don't need to keep p and q after the keys are generated however. The most common method of attack is to factor pq into p and q. If you can do this you can somehow find e from g^d mod pq. Remember that public key crypto is different then secret key crypto. The attack will have unlimited access to chosen plaintexts because they will have the encrypting key. Therefore the security is solely on the difficulty of finding the decrypting key. In RSA this is as difficult as factoring large composites (well that's a conjecture but...). Just like in Diffie-Hellman the security comes from finding the discrete logarithms. There are attacks where the modulus is too small, and attacks where e or d are to small. I would read a good description of RSA before
Cryptography-Digest Digest #782
Cryptography-Digest Digest #782, Volume #9 Sat, 26 Jun 99 18:13:04 EDT
Contents:
A few questions on RSA encryption (Gilad Maayan)
Re: generated pad for OTP? (Bill Unruh)
Re: A few questions on RSA encryption (S.T.L.)
Re: Tough crypt question: how to break AT&T's monopoly??? (Bill Unruh)
Re: generated pad for OTP? (Bill Unruh)
Re: Moores Law (a bit off topic) (S.T.L.)
Re: one time pad (S.T.L.)
Re: Tough crypt question: how to break AT&T's monopoly??? (S.T.L.)
Re: Moores Law (a bit off topic) (Horst Ossifrage)
Re: A few questions on RSA encryption (Bill Unruh)
A few questions on RSA encryption (Gilad Maayan)
Re: DES-NULL attack ("Mike Murray")
From: [EMAIL PROTECTED] (Gilad Maayan)
Subject: A few questions on RSA encryption
Date: Sat, 26 Jun 1999 20:59:20 GMT
I have a couple of questions on RSA, I hope someone will be able to
help.
1. I haven't been able to find any information on the relationship
between the number of bits encrypted by RSA, and the level of security
obtained. Let's say you're encrypting 20 bits with a 512 or 1024 bit
key. Is the small size of the plaintext relevant? Will the encrypted
message be easier to crack than, say, an entire document encoded by
the same RSA key?
2. Would it be at all possible to break an RSA cyphertext, knowing
neither the secret key, the public key, or the modulus?
3. Would it be possible to extrapolate an RSA key from a cyphertext,
if the plaintext was known? (assuming that neither the key used for
encryption nor its corresponding modulus are known).
4. If the modulus and public key were known, would available
cyphertext-plaintext make the cryptoanalysis process faster or easier?
5. (This one concerns DES, despite the topic :) Let's take a specific
encryption scenario, where a random key-seed is run through two
different functions. The two keys generated by this process, each 64
bits long, are used for a Triple-DES operation, the result of which is
sent through a non-secure medium. The key-seed is be encrypted using
RSA, and sent along with the enrypted message. If the two functions
aren't known to an attacker, and he manages to break the RSA code and
obtain the key-seed, would he be able to use that to extrapolate the
said functions from the encrypted message? I'm aware of the
key-management issues that arise from this scenario; my question
relates to a purely mathematical attack.
Many thanks,
Gilad Maayan
--
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: generated pad for OTP?
Date: 26 Jun 1999 21:28:20 GMT
In <[EMAIL PROTECTED]> Benjamin Goldberg
<[EMAIL PROTECTED]> writes:
>The "SecureRandom" generator produces 20 psuedo-random bytes at a time, by
>incrementing a 64-bit counter, and using a SHA-1 digest on that counter
>and a seed. While I know you can't reconstruct a message directly from a
This could be very easy to figure out if the seed is knowable or
guessable. The seed is essentially the key to this cypher, and with too
small a seed, this system will easily fall to exhaustive search. I would
also worry that the SHA of two strings which differ in so few bits might
be susceptible to breaking. SHA(seed+SHA(counter)) might be better-- but
slow.
Note, as will all such stream cyphers, you can never reuse your
key(seed).
--
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: A few questions on RSA encryption
Date: 26 Jun 1999 21:31:10 GMT
<>
Okay, I'll try.
<<1. I haven't been able to find any information on the relationship
between the number of bits encrypted by RSA, and the level of security
obtained. Let's say you're encrypting 20 bits with a 512 or 1024 bit
key. Is the small size of the plaintext relevant? Will the encrypted
message be easier to crack than, say, an entire document encoded by
the same RSA key?>>
Small plaintexts ARE a problem, as you anticipated. RSA is vulnerable to
chosen-plaintext attacks (I think that's what they are called), because ANYONE,
including the Adversary (the hypothesized cracker) can encrypt plaintexts of
their choice and notice if they match the ciphertext. For a 20-bit plaintext,
then the Adversary needs only try to encrypt 2^20 plaintexts before he finds
one that produces the same ciphertext. A larger document is therefore more
protected, and any document over, say, 256 bits is pretty darn safe.
<<2. Would it be at all possible to break an RSA cyphertext, knowing
neither the secret key, the public key, or the modulus?>>
I am not sure. Probably not. There are a heck of a lot possible keypairs, and
not knowing even the modulus makes it worse for the Adversary. Keeping even the
public key-and-modulus secret has to improve security, but I'm not sure by how
much.
<<3. Would it be possible to extrapolate an RSA key from a cyphertext,
if the plaintext was known? (assuming that neither the key used for
encryption nor its corresponding modulus are
Cryptography-Digest Digest #781
Cryptography-Digest Digest #781, Volume #9 Sat, 26 Jun 99 16:13:06 EDT Contents: Jim Gillogly on The Today Show: Kryptos (John L. Allen) Re: Kryptos article (B & J) Re: Kryptos article (wtshaw) Re: DES-NULL attack (Thomas Pornin) Re: DES-NULL attack (Thomas Pornin) Re: DES-NULL attack ([EMAIL PROTECTED]) Re: DES-NULL attack (Thomas Pornin) Re: Tough crypt question: how to break AT&T's monopoly??? (Dave Hazelwood) Re: DES-NULL attack (fungus) Re: DES-NULL attack (fungus) Re: Scramdisk cracked (A C Wilshere) Re: DES-NULL attack ([EMAIL PROTECTED]) Re: DES-NULL attack (Horst Ossifrage) Re: one time pad (Greg Ofiesh) Re: one time pad (Greg Ofiesh) Moores Law (a bit off topic) ([EMAIL PROTECTED]) Re: DES-NULL attack (William Tanksley) Re: one time pad (Greg Ofiesh) Re: one time pad (Greg Ofiesh) Re: one time pad (John Savard) Re: one time pad (Greg Ofiesh) Re: Tough crypt question: how to break AT&T's monopoly??? (Jayjames99) From: [EMAIL PROTECTED] (John L. Allen) Subject: Jim Gillogly on The Today Show: Kryptos Date: 25 Jun 1999 15:39:13 -0400 Jim Gillogly was on the NBC Today show this morning. There was a segment on the "Kryptos" sculpture outside the NSA, and he was billed as the guy who cracked part of the code using a computer. There was even a very brief "demo" of how decrypting is done. (There's no hiding now, Jim :-) John. -- _/JohnL\[EMAIL PROTECTED] : 9.5 billion pounds per sec to energy ~\Allen/~Fax: 516-575-7428: 1e22 stars = 22 solar masses per sec -- From: B & J <[EMAIL PROTECTED]> Subject: Re: Kryptos article Date: Sat, 26 Jun 1999 06:17:14 + I got quite interested in this KRYPTOS code thing, and was able to find the keys for the first 2 parts, but does anyone know if the keys mean anything at all , perhaps encrypted ? seems like gibberish to me - Ben -- From: [EMAIL PROTECTED] (wtshaw) Subject: Re: Kryptos article Date: Sat, 26 Jun 1999 00:50:25 -0600 In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote: > Jim Gillogly wrote: > > Reflecting on this, I realized it's utter garbage. The pool would > > swap up and down, not right and left. Never mind. > > Um, Jim, mirrors don't reverse in any particular direction. > Martin Gardner had a discussion of this in one of his books: > Why is your image in a flat mirror reversed left-to-right, > not top-to-bottom? (Think about it; it can produce one of > those moments of "enlightenment".) Congratulations Jim...now, time for recovery. If you come to Atlanta for the convention, please bring your costume; pardon me if I leave my best suit, my coveralls, at home. Something a mirror cannot fully reverse: .emoh ta ,sllarevoc ym ,tius tseb ym evael I fi em nodrap ;emutsoc ruoy gnirb esaelp ,noitnevnoc eht rof atnaltA ot emoc uoy fI .yrevocer rof emit ,won...miJ snoitalutargnoC -- It's always possible that a politician is acting out of principles. --Michael Kinsley of Slate.com -- From: [EMAIL PROTECTED] (Thomas Pornin) Subject: Re: DES-NULL attack Date: 26 Jun 1999 07:36:47 GMT According to <[EMAIL PROTECTED]>: > Let a plain text block contains only bits with NULL value. > > Then correspondent cipher block is well-defined function > of the encryption key, which can be recovered. Ok. Prove it. Here is the result of the DES encryption of 0 by a secret key of mine: e5d72a33650d160f Now show me the key. --Thomas Pornin -- From: [EMAIL PROTECTED] (Thomas Pornin) Subject: Re: DES-NULL attack Date: 26 Jun 1999 07:40:10 GMT According to JPeschel <[EMAIL PROTECTED]>: > Consider an intelligence agency with plenty of money to spend on > ASICs.* As usual: if some agency has so much power and is after me, the possibility that they could recover a DES key in a few days with a hardware worth dozens millions of dollars is the least of my concerns. They could kidnap me for much less. Anyway, the limit if generally considered to be about 80 bits. --Thomas Pornin -- From: [EMAIL PROTECTED] Subject: Re: DES-NULL attack Date: Sat, 26 Jun 1999 12:38:16 GMT In article <7l204q$mci$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Thomas Pornin) wrote: > As usual: if some agency has so much power and is after me, the > possibility that they could recover a DES key in a few days with a > hardware worth dozens millions of dollars is the least of my concerns. > They could kidnap me for much less. > > Anyway, the limit if generally considered to be about 80 bits. By whom? If a 64-bit key is not safe an 80-bit key is probably not safe. If we are to follow the skeptism. You know it's funny. I work on crypto stuff almost all the time, but I hardly ever use it myself... When I do it's for PGP messages and such. 64-bit keys will keep my
