Cryptography-Digest Digest #388, Volume #13 Mon, 25 Dec 00 03:13:01 EST
Contents:
Re: Possible AONT? ("Matt Timmermans")
Re: All irreducible polys of degree 32 over GF(2) (D. J. Bernstein)
Re: Foolproof Quantum Cryptography (Simon Jenkins)
Re: Foolproof Quantum Cryptography (Steve Portly)
Re: All irreducible polys of degree 32 over GF(2) (Bryan Olson)
Merry Christmas (Simon Johnson)
Re: Merry Christmas ("John A. Malley")
Re: Merry Christmas ("Tom ST Denis")
Re: Merry Christmas ("Matt Timmermans")
Re: Possible AONT? (Benjamin Goldberg)
Re: All irreducible polys of degree 32 over GF(2) (Benjamin Goldberg)
Re: RSA == hash function? ([EMAIL PROTECTED])
Re: RSA == hash function? ([EMAIL PROTECTED])
Re: Merry Christmas (David A Molnar)
----------------------------------------------------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Possible AONT?
Date: Sun, 24 Dec 2000 19:50:50 GMT
"Tom ST Denis" <[EMAIL PROTECTED]> wrote in message
news:fBo16.12643$[EMAIL PROTECTED]...
> What the heck are you doing anyways? Seems overly complicated and insane.
> If you output the key then what is the point?
AONT is short for "all or nothing transform". The goal is to ensure that an
attacker needs _all_ the transformed data before he can get any of the
plaintext. It is often used to encrypt symmetric keys with RSA -- the key
is padded with random data to the size of the RSA modulus, an AONT is
performed, and the result is encrypted. Without the AONT, it's conceivable
that someone could recover the encrypted key by devising an effective attack
against only the lower bits of the RSA encryption.
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: 24 Dec 2000 19:59:52 GMT
One can multiply or divide two polynomials of degree at most d over any
field using O(d log d log log d) coefficient operations.
One can, therefore, compute the polynomial q=(x-r_1)...(x-r_d) given
r_1,...,r_d using O(d log^2 d log log d) coefficient operations:
multiply (x-r_1)...(x-r_{d/2}) by (x-r_{d/2+1})...(x-r_d).
Similarly, given c_1,...,c_d and r_1,...,r_d, one can compute the sum of
c_j q/(x-r_j) using O(d log^2 d log log d) coefficient operations.
Furthermore, given r_1,...,r_d and a polynomial p of degree smaller than
d, one can compute p(r_1),...,p(r_d) using O(d log^2 d log log d)
coefficient operations: recursively handle p mod (x-r_1)...(x-r_{d/2})
and p mod (x-r_{d/2+1})...(x-r_d).
Now assume that r_1,...,r_d are distinct, and that p is a polynomial of
degree smaller than d. Then p is the sum of (p(r_j)/q'(r_j)) q/(x-r_j).
Given r_1,...,r_d and p(r_1),...,p(r_d), one can compute q, then q',
then each q'(r_j), then p(r_j)/q'(r_j), and finally p, using
O(d log^2 d log log d) coefficient operations.
---Dan
------------------------------
Date: Sun, 24 Dec 2000 20:52:17 +0000
From: Simon Jenkins <[EMAIL PROTECTED]>
Subject: Re: Foolproof Quantum Cryptography
John Savard wrote:
> On 23 Dec 2000 20:10:37 GMT, [EMAIL PROTECTED] (Bill Unruh) wrote,
> in part:
>
> >Hype vastly exceeds reality. Making single photons has nothing to do
> >with quantum computing. Such a device may or may not be useful in a
> >quantum computer.
>
> But quantum cryptography has nothing to do with quantum computers
> either.
>
> Looking at the cited article, it claims these single photons are
> useful in both, but it's the cryptography (the EPR one-time-pad
> sharing stuff) that is 'foolproof' in that the interception of a
> single photon will always be detected.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
Just to sidetrack a bit on quantum cryptography (of which I am no
expert), it seems to me that, if I wanted to stop anybody using it, I
would just intercept all their messages. They would be aware the messages
had been intercepted because (I think) the photon states would have
changed and the message they received with therefore be garbage, forcing
them to use a more accessible system.
Or maybe I'm wrong.
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: Foolproof Quantum Cryptography
Date: Sun, 24 Dec 2000 16:37:42 -0500
Simon Jenkins wrote:
> John Savard wrote:
>
> > On 23 Dec 2000 20:10:37 GMT, [EMAIL PROTECTED] (Bill Unruh) wrote,
> > in part:
> >
> > >Hype vastly exceeds reality. Making single photons has nothing to do
> > >with quantum computing. Such a device may or may not be useful in a
> > >quantum computer.
> >
> > But quantum cryptography has nothing to do with quantum computers
> > either.
> >
> > Looking at the cited article, it claims these single photons are
> > useful in both, but it's the cryptography (the EPR one-time-pad
> > sharing stuff) that is 'foolproof' in that the interception of a
> > single photon will always be detected.
> >
> > John Savard
> > http://home.ecn.ab.ca/~jsavard/crypto.htm
>
> Just to sidetrack a bit on quantum cryptography (of which I am no
> expert), it seems to me that, if I wanted to stop anybody using it, I
> would just intercept all their messages. They would be aware the messages
> had been intercepted because (I think) the photon states would have
> changed and the message they received with therefore be garbage, forcing
> them to use a more accessible system.
>
> Or maybe I'm wrong.
A denial of service attack would be practical in most cases however one of
the articles mentioned the primary use would be for rekeying satellites.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: Sun, 24 Dec 2000 22:35:41 GMT
Benjamin Goldberg wrote:
> Bryan Olson wrote:
> >
> > Benjamin Goldberg wrote:
> > > Curiously, this method seems to be a way to have a secure unicast
> > > file transmission [...]
> >
> > I think you are jumping to an unwarranted conclusion.
>
> Note that I only said *seems* to be. I wouldn't use this
> method unless I was *sure* that it was good -- that is,
> until I'd seen some cryptanalysis on it.
Noted. I hold that saying "seems to be ... secure" before
doing any analysis is nonsense. If we have not looked, it
does not seem to be anything.
> > Then if the attacker knows the file, he can get the
> > generator output.
>
> Eh? How? He's got a bunch of crc's of the file. Given a file, and a
> CRC, how do you reproduce the crc polynomial?
It will not be unique for every output, but will expose many
outputs and limit others to several candidates. That's
enough to break most non-cryptographic generators, including
the Mersenne Twister.
Finding the possible CRC polynomials requires finding small
factors. In this case we could even do it by trial
division.
> I suspect that only if the attacker knows the ENTIRE
> message might he be able to get the generator output.
Even if your suspicion is true, that's a broken cipher.
> If a different seed is used with each message, then this
> is irrelevant.
Wrong. For example it allows an attacker to distinguish
among several candidate messages.
> Logically, one should use an IV, and hash it with the
> secret key to create the MT seed -- this will result
> in totally unrelated MT seeds for each message.
[...]
> Well, joining the IV and seed as they are done in
> ciphersaber would be a Bad Idea, but I don't think that
> the scheme is too terrible.
Shouldn't that be "was a Bad Idea"? That is what you
proposed right? I responded based on the scheme you
posted. Do you agree that given a known plaintext of a few
kilobytes, the attacker can find generator output, recover
the state and thus the key, and then use that key to decrypt
other messages?
Now you want to add the hash function to generate session
keys. I'd still reject the revised method, just based on
the ability to distinguish the ciphertext of a known message
from uniform noise of the same size.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Merry Christmas
Date: Sun, 24 Dec 2000 23:53:41 GMT
I understand for some of you, that it won't be christmas when you
recieve this message (because your x number of hours behind england)
but i'd like to wish all the readers of sci.crypt a very merry
christmas and a happy new-year.
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Merry Christmas
Date: Sun, 24 Dec 2000 17:48:54 -0800
Here here!
Merry Christmas and a Happy New Year to you, too,
and to all of our sci.crypt friends, colleagues and compatriots the
world over!
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: "Tom ST Denis" <[EMAIL PROTECTED]>
Subject: Re: Merry Christmas
Date: Mon, 25 Dec 2000 02:29:39 GMT
"John A. Malley" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Here here!
> Merry Christmas and a Happy New Year to you, too,
> and to all of our sci.crypt friends, colleagues and compatriots the
> world over!
Merry X-Mas All. May the new year bring much joy, fun and drunken bouts of
coding! (I don't drink myself but I heard it's even more fun when you can't
remember what you wrote or why!)
Tom
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Merry Christmas
Date: Mon, 25 Dec 2000 03:42:48 GMT
Well, It'll be Christmas here in an hour or so (why oh why am I checking
usenet?!?!). Oh well, Merry Christmas Everyone!
"Tom ST Denis" <[EMAIL PROTECTED]> wrote in message
news:niy16.15143$[EMAIL PROTECTED]...
>
> "John A. Malley" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Here here!
> > Merry Christmas and a Happy New Year to you, too,
> > and to all of our sci.crypt friends, colleagues and compatriots the
> > world over!
>
> Merry X-Mas All. May the new year bring much joy, fun and drunken bouts
of
> coding! (I don't drink myself but I heard it's even more fun when you
can't
> remember what you wrote or why!)
>
> Tom
>
>
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Possible AONT?
Date: Mon, 25 Dec 2000 06:44:12 GMT
Matt Timmermans wrote:
>
> "Tom ST Denis" <[EMAIL PROTECTED]> wrote in message
> news:fBo16.12643$[EMAIL PROTECTED]...
> > What the heck are you doing anyways? Seems overly complicated and
> > insane.
> > If you output the key then what is the point?
>
> AONT is short for "all or nothing transform". The goal is to ensure
> that an attacker needs _all_ the transformed data before he can get
> any of the plaintext. It is often used to encrypt symmetric keys with
> RSA -- the key is padded with random data to the size of the RSA
> modulus, an AONT is performed, and the result is encrypted. Without
> the AONT, it's conceivable that someone could recover the encrypted
> key by devising an effective attack against only the lower bits of the
> RSA encryption.
Additionally, AONT had an important use before the crypto export
restrictions were lifted. Since AONT is *not* an encryption scheme, but
a reversible transformation that requires no user key, it is/was not
limited to 40 bits. Thus, one could perform AONT on a file, and then
encrypt it with 40 bit DES, and the AONT would seriously slow down an
attacker who was using brute force -- he would have to trial decrypt the
entire file to see if his guessed key was correct.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: All irreducible polys of degree 32 over GF(2)
Date: Mon, 25 Dec 2000 07:03:06 GMT
Bryan Olson wrote:
>
> Benjamin Goldberg wrote:
> > Bryan Olson wrote:
> > >
> > > Benjamin Goldberg wrote:
> > > > Curiously, this method seems to be a way to have a secure
> > > > unicast file transmission [...]
> > >
> > > I think you are jumping to an unwarranted conclusion.
> >
> > Note that I only said *seems* to be. I wouldn't use this
> > method unless I was *sure* that it was good -- that is,
> > until I'd seen some cryptanalysis on it.
>
> Noted. I hold that saying "seems to be ... secure" before
> doing any analysis is nonsense. If we have not looked, it
> does not seem to be anything.
>
> > > Then if the attacker knows the file, he can get the
> > > generator output.
> >
> > Eh? How? He's got a bunch of crc's of the file. Given a file, and
> > a CRC, how do you reproduce the crc polynomial?
>
> It will not be unique for every output, but will expose many
> outputs and limit others to several candidates. That's
> enough to break most non-cryptographic generators, including
> the Mersenne Twister.
>
> Finding the possible CRC polynomials requires finding small
> factors. In this case we could even do it by trial
> division.
>
> > I suspect that only if the attacker knows the ENTIRE
> > message might he be able to get the generator output.
>
> Even if your suspicion is true, that's a broken cipher.
>
> > If a different seed is used with each message, then this
> > is irrelevant.
>
> Wrong. For example it allows an attacker to distinguish
> among several candidate messages.
>
> > Logically, one should use an IV, and hash it with the
> > secret key to create the MT seed -- this will result
> > in totally unrelated MT seeds for each message.
> [...]
> > Well, joining the IV and seed as they are done in
> > ciphersaber would be a Bad Idea, but I don't think that
> > the scheme is too terrible.
>
> Shouldn't that be "was a Bad Idea"? That is what you
> proposed right? I responded based on the scheme you
> posted. Do you agree that given a known plaintext of a few
> kilobytes, the attacker can find generator output, recover
> the state and thus the key, and then use that key to decrypt
> other messages?
Yes, yes, and no. Given a *complete* known plaintext, the entire file,
I think it may be possible for the attacker can find the generator
output... but I don't yet see how it might be done, and so am not yet
going to reject the scheme.
Each seperate message needs it's own independent key. (Or at least
apparently independent, as with securely hashing a fixed secret key with
a unique known IV).
> Now you want to add the hash function to generate session
> keys. I'd still reject the revised method, just based on
> the ability to distinguish the ciphertext of a known message
> from uniform noise of the same size.
Being able to distinguish from random is indeed a valid reason to reject
a scheme, except you have not described exactly (or even approximitly )
how to do this. Earlier, I said:
> > I suspect that only if the attacker knows the ENTIRE
> > message might he be able to get the generator output.
And you responded:
> Even if your suspicion is true, that's a broken cipher.
But I did not say that I *knew* that the attacker knowing the entire
message would automatically enable him to get the generator output, only
that it MIGHT, concievably, be possible. Just as it might be possible
to factor RSA in less time than GNFS uses. It might be possible to get
discrete logarithms easily. However, I certainly don't know of a way.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA == hash function?
Date: Mon, 25 Dec 2000 06:58:18 GMT
In article <sXm16.11676$[EMAIL PROTECTED]>,
"Tom ST Denis" <[EMAIL PROTECTED]> wrote:
>
> <[EMAIL PROTECTED]> wrote in message
news:924mjv$okj$[EMAIL PROTECTED]...
> > I think RSA cannot be considered as a hash function because its
input
> > and output length is a variable depending on the modulo n. Hash
> > function should take variable input length and produce fixed length
> > output.
> This is simply not true. The size of RSA parameters are always
fixed. While
> it's true in some cases they can be optimized but 99% of the time they
> can't. RSA plaintext and ciphertext ARE THE SAME SIZE!
I agree that RSA with cipher block chaining can take variable input
length. I overlook this case.
Let's scope down the hash function to one-way hash function.
Can RSA in block chaining mode be a one-way hash function?
For the hashing with RSA in block chaining mode, the size of the last
block is equal to the size of the moduli n. Since different RSA hashing
has different moduli n, therefore we have varible size output for
different RSA hashing. This varible size output is contrast to the the
definition* of a one-way hash function that returns fixed length output.
Then we should ask: a one-way hash function must produce a fixed
length output? Why?
Thanks!
*page 429 Applid Cryptography(96)
W.S.Chong
[EMAIL PROTECTED]
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA == hash function?
Date: Mon, 25 Dec 2000 07:53:23 GMT
In article <9256mi$2kf$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> In article <924mjv$okj$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > I think RSA cannot be considered as a hash function because its
input
> > and output length is a variable depending on the modulo n. Hash
> > function should take variable input length and produce fixed length
> > output.
> >
> > please comment.
> >
> > W.S. Chong
> > [EMAIL PROTECTED]
> >
> > Sent via Deja.com
> > http://www.deja.com/
> >
>
> Nope, you can use RSA as a hash function. But you have to make key
pair
> for RSA. You would then use it as a compression function, like
> described in Applied Cryptography.
> Personally, i think using RSA as a hash function is dodgy. It would be
> hard to convice someone that you havn't computed the private key,
which
> would allow you to create collisions and reverse the hash. If you want
> a complexity theortic hash, use a discrete log problem as the
> compression function.
With the RSA private key, what's the probability of creating a
collision in the RSA ciphertext?
W.S.Chong
[EMAIL PROTECTED]
Sent via Deja.com
http://www.deja.com/
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Merry Christmas
Date: 25 Dec 2000 07:41:35 GMT
Tom ST Denis <[EMAIL PROTECTED]> wrote:
> Merry X-Mas All. May the new year bring much joy, fun and drunken bouts of
> coding! (I don't drink myself but I heard it's even more fun when you can't
> remember what you wrote or why!)
This has not been my experience, not that I've tried it more than once or
twice...
That being said, happy holidays!
(and a crypto question: what does Santa use to keep his list of
"naughty" and "nice" children private? how does he look up a kid in the
database?)
-David
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
