Cryptography-Digest Digest #791, Volume #9 Mon, 28 Jun 99 11:13:05 EDT
Contents:
Interesting RSA question (Gilad Maayan)
Re: The One-Time Pad Paradox (Coen Visser)
Re: Tough crypt question: how to break AT&T's monopoly??? ([EMAIL PROTECTED])
Re: xtea ([EMAIL PROTECTED])
Re: Interesting RSA question (Ed Yang)
Re: A few questions on RSA (Ed Yang)
Re: Moore's Trend ([EMAIL PROTECTED])
Re: Tough crypt question: how to break AT&T's monopoly??? (JPeschel)
Re: Sexual Contact Privacy :) ( Doug Goncz)
Re: DES-NULL attack (Patrick Juola)
Re: A few questions on RSA encryption (Patrick Juola)
Re: determining number of attempts required (Keith A Monahan)
Re: xtea (Peter Gunn)
Re: A few questions on RSA (Bob Silverman)
Re: Hamming Weight (Michael J. Fromberger)
Re: The One-Time Pad Paradox ([EMAIL PROTECTED])
Re: Tough crypt question: how to break AT&T's monopoly??? ([EMAIL PROTECTED])
Re: Interesting RSA question ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Gilad Maayan)
Subject: Interesting RSA question
Date: Mon, 28 Jun 1999 10:30:25 GMT
In continuation to the 'A few questions on RSA' thread, I'd like to
ask if anyone knows whether there's a fixed relationship between key
sizes, plaintext sizes, and cyphertext sizes, in RSA.
Let's take the following unlikely scenario: You take a 20-bit
cyphertext, encrypt it with an RSA key (1024-bit modulus), and get a
roughly 1000-bit-long cyphertext. I've been made aware of the fact
that a cyphertext usually baloons to the size of the key, regardless
on the plaintext length.
Now, say you want to go the opposite route: Take a random 1000-bit
long cyphertext, and decrypt it using the corresponding secret key, to
get a 20-bit number. Naturally, this won't be much more than a pretty
random 20-bit number, but it suits my purposes.
So, my question is: Knowing both public and secret key lengths, what
formula could be used to determine the exact length of the 1000-odd
random number from which you could obtain 20 bits through decryption?
------------------------------
From: [EMAIL PROTECTED] (Coen Visser)
Subject: Re: The One-Time Pad Paradox
Date: 28 Jun 1999 11:10:50 GMT
[EMAIL PROTECTED] (John Savard) writes:
>[EMAIL PROTECTED] (S.T.L.) wrote, in part:
>>Moral of this story: You were absolutely correct that munging a one-time-pad
>>spoils its perfection. "Null keys" or "similar plaintext producing keys" don't
>>change that, and in my eyes aren't a paradox because of the existence of
>>"completely different plaintexts".
>I know you disagree, but I think that we must also take into account
>that we don't live in a perfect world, and an adversary may not know
>that we're using the one-time-pad for our messages.
This way of thinking leads to an ever increasing amount of kludges to the
one-time-pad. Suppose you want to exclude the all zero random string, then
you also have to exclude the random bitstring that transforms your plaintext
into the same text with 1 character shifted or the bitstring that reverses
your plaintext or the bitstring with only zero's on the even positions or ...
Regards,
Coen Visser
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Tough crypt question: how to break AT&T's monopoly???
Date: Mon, 28 Jun 1999 11:44:58 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (JPeschel) wrote:
> If that's what you meant, you're mistaken. Files type with known
headers
> like MPGs and JPGs make a known-plaintext attack even easier.
>
I thought the attack on PKZIP required 400 plaintexts? MP3s only have
a few bytes do they not?
Either case it was an example of the type of data you can't hack in
PKZIP (except the known headers).
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: xtea
Date: Mon, 28 Jun 1999 11:41:31 GMT
<snip>
Looking at the XTEA paper now...
The lines are
y += ((z << 4) ^ (z >> 5)) + (z ^ sum) + K[sum & 3];
sum += DELTA;
z += ((y << 4) ^ (y >> 5)) + (y ^ sum) + K[(sum >> 11) & 3];
I added brackets to show the order of the ops. There are other ways to
do the same thing, but most C compilers like the above.
As long as you use substraction in the reverse order decryption should
work fine. Consider everything to the right of += as the F function.
It doesn't need to be invertible, just reproducable.
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Ed Yang <[EMAIL PROTECTED]>
Subject: Re: Interesting RSA question
Date: Mon, 28 Jun 1999 04:50:37 -1000
Gilad Maayan wrote:
> So, my question is: Knowing both public and secret key lengths, what
> formula could be used to determine the exact length of the 1000-odd
> random number from which you could obtain 20 bits through decryption?
Using a 1024 bit key, you would use a 1024 bit ciphertext to decrypt
to get the 20 bit plaintext. Since finite arithmetic is used, during
exponentiation c^d mod n all inputs and outputs are 1024 bits.
If your plaintext only has 20 useful bit, it is padded with 1004
extra bits before encrypting p^e mod n = c . The padding should not
be all zeros, but some standardized padding which the software
comprehends, you do need to comprehend it to use the Public Key
Infrastucture standard software (PKI). (See www.rsa.com)
The modulo function limits all numbers involved to 1024 bits.
Raising a 20 bit number to a 1024 bit exponent give 1044 bits
as a result but then the mod n step reduces the result to a 1024 bit
number.
--
Oxygen : Love It Or Leave It !
------------------------------
From: Ed Yang <[EMAIL PROTECTED]>
Subject: Re: A few questions on RSA
Date: Mon, 28 Jun 1999 04:55:07 -1000
Gilad Maayan wrote:
>
> >... Recovering phi(n) from n alone is as hard as factoring.
>
> Phew... That's a relief. My whole system collapsed under me when I
> thought e and d were inverses :)
>
> Many thanks,
> Gilad Maayan
d is the inverse of e mod (phi(n)), and phi(n) is secret, n is public.
See the FAQ at www.rsa.com
--
Oxygen : Love It Or Leave It !
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Moore's Trend
Date: Mon, 28 Jun 1999 11:50:11 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> Well, when DES was proposed, the people proposing it claimed that 56
> bits was good enough; _others_, but yes, at that time, said the key
> length was adequate. However, the most prominent objectors recommended
> that we encrypt everything in RSA instead of using a conventional
> cipher with a bigger key...
The first DES proposal had a 112 bit key according to AC. If that
keyspace was flat that would be a nice keysize, even now.
> And there's no way of knowing that it will take a century before
> quantum computers become practical.
Yes but how many citizens have access to a quantum computer. How much
time and money does it cost to brute force a single key? This requires
3 things (bare min)
1) Quantum computers become reliable
2) They build a DES/AES 'cracker' program
3) They can put ciphertext in, and set the rules for the output.
I think those steps will take a long time. For the average job blow
128-bit keyspace is impossible to search (well infeasible).
> Can anything, short of the OTP, resist a quantum computer? Is anyone
> out there wrestling with this question (I'm trying to, but I confess I
> don't quite have the equipment to grapple with it...).
How do you make the OTP keystream though? There may be attack on the
generator.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Tough crypt question: how to break AT&T's monopoly???
Date: 28 Jun 1999 12:45:38 GMT
>[EMAIL PROTECTED] writes:
>I thought the attack on PKZIP required 400 plaintexts? MP3s only have
>a few bytes do they not?
>
Nope, you need at least 13 bytes. Since you like to read papers you might
want to look the Kocher/Biham paper," A Known Plaintext Attack on the
PKZIP Stream Cipher," from 1994. It's on Eli's site. Peter Conrad implemented
the attack. He includes source code and a binary. This seems beneficial to
look at if you're interested in implementing real attacks on ciphers.
http://www.unix-ag.uni-kl.de/~conrad/krypto/pkcrack.html
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] ( Doug Goncz )
Subject: Re: Sexual Contact Privacy :)
Date: 28 Jun 1999 13:52:17 GMT
Well, thanks for the perspectives. The only thing that wasn't suggested is a
rapidly mutating virus, a benign, sexually transmitted virus, that (who?) could
be "disassembled" by DNA analysis and compared to other samples, establishing a
link between two people.
All of you are right. This is just not practical. The next time I raise the
issue here, I will try to frame it more philosophically, and in cryptological
terms.
By the way, I didn't suggest that the government keep records, only indicated
that a government might want to. I put that first in the original post to
create controversy, and it did. A real attention grabber.
"Mama, baby. Papa, maybe."
Yours,
Doug Goncz
Experimental Machinist (DOT 600.260-022)
Replikon Research (USA 22044-0094)
http://users.aol.com/DGoncz or /ReplikonVA
The ocean is the world's longest runway...
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: DES-NULL attack
Date: 28 Jun 1999 09:48:08 -0400
In article <[EMAIL PROTECTED]>,
Horst Ossifrage <[EMAIL PROTECTED]> wrote:
>Thomas Pornin wrote:
>
>> Agreed. But Moore's law (*) will keep on getting it less secure every
>> year. This explains the 128-bit keys for the AES.
>
>It is not a law it is a trend. Please quote Moore when he claimed it
>was a law. It was called a law by laymen.
No one claims their own work as a law, especially today; that's
regarded as arrogant. Similarly, no one names their own work after
themselves -- the Brill tagger, although invented by Brill, was
actually named that by the number of researchers who applied and
extending his work.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: A few questions on RSA encryption
Date: 28 Jun 1999 09:51:44 -0400
In article <[EMAIL PROTECTED]>,
Gilad Maayan <[EMAIL PROTECTED]> wrote:
>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?
Very much so. I merely perform 2^20 trial encryptions with your
(known) public key and determine which one matches the observed
cyphertext.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: determining number of attempts required
Date: 28 Jun 1999 13:55:26 GMT
S.T.L. ([EMAIL PROTECTED]) wrote:
: I would have had to use would have been quite nasty. Good thing I didn't
: encrypt anything important with it.
Unfortunately, there is something important in my files...
: That makes sense. Nice setup you have there, actually.
Yeah, it might be kind of hokey, but it works.
: However, I believe that
: if you can code C, making your own custom cracker would result in a net
: speedup. :-D That'd be my suggestion.
Heck yeah, that would almost definitely improve my search speed. I can code
C, but I don't know how hard it would be to implement the algorithm. I would
also have to write some sort of recognizing procedure, whereas I would know
I had the proper key by seeing some sort of "BestCrypt" header. I suppose
a little studying of the program could yield results.
What Predicaments I get myself into.
Keith
: -*---*-------
: S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^3021377 - 1 is PRIME!
: Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
: "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, the Union of Quantum Mechanics, and
: the Holy Order of the Catenary.
: 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: Peter Gunn <[EMAIL PROTECTED]>
Subject: Re: xtea
Date: Mon, 28 Jun 1999 14:52:30 +0100
[EMAIL PROTECTED] wrote:
> <snip>
> Looking at the XTEA paper now...
>
> The lines are
>
> y += ((z << 4) ^ (z >> 5)) + (z ^ sum) + K[sum & 3];
> sum += DELTA;
> z += ((y << 4) ^ (y >> 5)) + (y ^ sum) + K[(sum >> 11) & 3];
>
> I added brackets to show the order of the ops. There are other ways to
> do the same thing, but most C compilers like the above.
>
> As long as you use substraction in the reverse order decryption should
> work fine. Consider everything to the right of += as the F function.
> It doesn't need to be invertible, just reproducable.
Tom,
you've added brackets to show how you think the expressions
should be evaluated, but since this looks to be different from the
operator precedence of ANSI C, how did you decide that was
what Wheeler & Needham intended?
Perhaps they've posted an updated paper?
tata
PG.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: A few questions on RSA
Date: Mon, 28 Jun 1999 14:02:28 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Gilad Maayan) wrote:
> Take the following encryption scenario:
> A 20 bit cyphertext is encrypted into a 20 bit cyphertext using a 1024
> bit RTS pubic key.
I assume you mean 20 bit plaintext.
This is your first false assumption.
(1) The plaintext is ALWAYS padded to the length of the modulus before
being encrypted.
(2) The ciphertext is always going to be about the same length as the
modlus. It will be 1 bit less with p = 1/2, 2 bits less with p = 1/4
etc.
The public exponent is only about 100 bits long;
> the secret exponent would be around 900 (if I'm not mistaken).
You are mistaken.
(3) The secret exponent will be about the same length as the modulus.
Anyhow,
> we're talking about a drastically small public key, and a
> correspondingly large secret key.
The secret key always is and always MUST be large.
>
> I'm assuming, in the above scenario, that all of the following are
> true.
<snip>
>
> 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.
The modulus is always assumed to be public.
Knowing the length of the plaintext does not provide any info that
anyone knows how to attack.
>
> 2. Let's assume the attacker knows the plaintext but not the modulus
> or the public key.
But the modulus is always known. That is the point of a public-key
system.
>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)
Try again. The size of the possible keyspace is of the order 10^600
There are about 10^303 possible moduli and 2^1023 (or so) possible
public exponents.
<rest deleted>
May I suggest you do some reading about the RSA encryption scheme?
The Handbook of Applied Cryptography would be a good starting place.
--
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/
Share what you know. Learn what you don't.
------------------------------
From: Michael J. Fromberger <[EMAIL PROTECTED]>
Subject: Re: Hamming Weight
Date: 28 Jun 1999 14:14:41 GMT
In <7l6bil$180$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>In article <7l672p$vra$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
>> What is a Hamming Weight and how does one calculate it?
>Hamming weight is the number of different bits in two bit vectors. It
>is calculated by performing
>(1) C = A xor B
>(2) Count the 1 bits in C.
>The result from #2 is the hamming weight.
Actually, this is not quite correct. What Tom is describing here is
Hamming -distance-, not Hamming -weight-. "Hamming weight" is simply
the number of set bits in a bit-sequence. The typical definition of
Hamming distance is the number of single-bit changes required to
transform one bit-sequence into the other
Cheers,
-M
--
Michael J. Fromberger Software Engineer, Thayer School of Engineering
sting <at> linguist.dartmouth.edu http://www.dartmouth.edu/~sting/
l3QkcsgdIMBlBFgAdXcOAeOoUnPk+TSGaRRThHfAa0bUj6Sgss2eDVGqVrDgME1XciSZMv8p
Remove clothing if you wish to reply to this message via e-mail.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The One-Time Pad Paradox
Date: Mon, 28 Jun 1999 14:50:36 GMT
In article <7l7l7q$soi$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Coen Visser) wrote:
> This way of thinking leads to an ever increasing amount of kludges to
the
> one-time-pad. Suppose you want to exclude the all zero random string,
then
> you also have to exclude the random bitstring that transforms your
plaintext
> into the same text with 1 character shifted or the bitstring that
reverses
> your plaintext or the bitstring with only zero's on the even
positions or ...
Then it's no longer a OTP. The chances of getting any key would be 1
in 2^8n. for message of about 100 bytes that 1 in 2^800 or
1.499696813895630954817644437628e-241. So it's highly improbable.
Most times RNG's like RC4 which simulate a OTP type operation will not
produce all zeroes with a high prob. Sometimes it is just not
possible. Dunno.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Tough crypt question: how to break AT&T's monopoly???
Date: Mon, 28 Jun 1999 14:52:23 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (JPeschel) wrote:
> Nope, you need at least 13 bytes. Since you like to read papers you
might
> want to look the Kocher/Biham paper," A Known Plaintext Attack on the
> PKZIP Stream Cipher," from 1994. It's on Eli's site. Peter Conrad
implemented
> the attack. He includes source code and a binary. This seems
beneficial to
> look at if you're interested in implementing real attacks on ciphers.
I already have the paper but have not read it yet. I just read the
basic info from AC.
Maybe I will read the paper. Thanks for the hint.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Interesting RSA question
Date: Mon, 28 Jun 1999 14:59:38 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Gilad Maayan) wrote:
> In continuation to the 'A few questions on RSA' thread, I'd like to
> ask if anyone knows whether there's a fixed relationship between key
> sizes, plaintext sizes, and cyphertext sizes, in RSA.
The plaintext can be any thing from 0 to pq - 1. It should be padded
so dictionary attacks are not possible. Ideally you want to have
enough padding such that you will never (never!) get the same
ciphertext for any key.
> Let's take the following unlikely scenario: You take a 20-bit
> cyphertext, encrypt it with an RSA key (1024-bit modulus), and get a
> roughly 1000-bit-long cyphertext. I've been made aware of the fact
> that a cyphertext usually baloons to the size of the key, regardless
> on the plaintext length.
20-bit ciphertext would require a 20-bit modulus. The input
(plaintext) can be between 0 to pq - 1. If it's less then pq - 1 then
padding must be performed. Kinda like a salt.
The ciphertext will alwats contain 1024 bits (or whatever the mod is)
of information. It cannot be compressed.
> So, my question is: Knowing both public and secret key lengths, what
> formula could be used to determine the exact length of the 1000-odd
> random number from which you could obtain 20 bits through decryption?
The idea is you cannot determine the length of the message, because
each message as 1024 - log2(m) bits of padding. The padding is random,
so no two messages (well before the padding strings run out) are
encrypted to the same. i.e you can not tell the random padding from
the plaintext in any ciphertext. If this is true then you cannot tell
the message length or contents.
For example encrypting random length keys (lets say for example in PGP)
you will not be able to determine the symmetric key length from the
ciphertext. You will most likely have to attack the RNG that makes the
key length or keys...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
** 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
******************************
