Cryptography-Digest Digest #316, Volume #10 Sun, 26 Sep 99 17:13:04 EDT
Contents:
Re: frequency of prime numbers? ("Richard Parker")
Re: EAR Relaxed? Really? ("Aaron Swartz")
--- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein)
Compress before Encryption (SCOTT19U.ZIP_GUY)
Introductory Crypto Site ([EMAIL PROTECTED])
peekboo (Tom St Denis)
Paul Black's Dictionary of Algorithms and Data Structures (Alex Vinokur)
Need advice for encrypting information (yoni)
Re: low diffie-hellman exponent (jerome)
Re: Need advice for encrypting information (jerome)
Re: Increasing password security dramatically without making it harder to (David P
Jablon)
Re: Schrodinger's Cat and *really* good compression (Mok-Kong Shen)
Re: steganography (Mok-Kong Shen)
Re: Purdue's Large Number (John M. Gamble)
Re: Need advice for encrypting information
Re: low diffie-hellman exponent ("Michael Scott")
Re: SNAKE Web Page (Peter Gunn)
Re: SNAKE Web Page (Paul Onions)
----------------------------------------------------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Date: Sun, 26 Sep 1999 03:34:49 GMT
[EMAIL PROTECTED] (Donald Welsh) wrote:
>Jerry Leichter <[EMAIL PROTECTED]> wrote:
>>(In fact, even strong results are now
>>known - concering independence, and actual bounds on the size of
>>provable statements (Greg Chaitin's work).)
>
> Jerry, I'd be interested to read about that. Would you please post or
> email references?
There is a good set of links and references on Dr. Chaitin's home page
at the following URL:
<http://www.umcs.maine.edu/~chaitin/
------------------------------
From: "Aaron Swartz" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: EAR Relaxed? Really?
Date: Sun, 26 Sep 1999 03:55:22 GMT
In article <[EMAIL PROTECTED]> ,
[EMAIL PROTECTED] (wtshaw) wrote:
> In article <7sggil$gn3$[EMAIL PROTECTED]>, Greg <[EMAIL PROTECTED]> wrote:
>
> I wrote:
>>
>> > Note the latest ad from Apple reflecting the government's
>> > philosophy that good computers should not be exported. It is
>> > interests of our government foreign computers be vulnerable.
>>
>> Where can I see this at? Is it on the web?
>>
> It's playing on cable here, could be a reflected local channel. Next time
> I see it, I will note the particuliars.
It's on the web at:
http://www.apple.com/powermac/tanks.html
Requires QuickTime
Aaron Swartz <[EMAIL PROTECTED]>|<http://swartzfam.com:81/go/echelon>
<http://www.swartzfam.com/lineup/>|Digital Nuclear Bomb to hit Echelon
<http://www.swartzfam.com/aaron/> |Cracking RC5 without NSA Help
ICQ: 33158237 | AIM: Jedi of Pi |Tapping Civilian Communications
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: talk.politics.crypto
Subject: --- sci.crypt charter: read before you post (weekly notice)
Date: 26 Sep 1999 05:00:35 GMT
sci.crypt Different methods of data en/decryption.
sci.crypt.research Cryptography, cryptanalysis, and related issues.
talk.politics.crypto The relation between cryptography and government.
The Cryptography FAQ is posted to sci.crypt and talk.politics.crypto
every three weeks. You should read it before posting to either group.
A common myth is that sci.crypt is USENET's catch-all crypto newsgroup.
It is not. It is reserved for discussion of the _science_ of cryptology,
including cryptography, cryptanalysis, and related topics such as
one-way hash functions.
Use talk.politics.crypto for the _politics_ of cryptography, including
Clipper, Digital Telephony, NSA, RSADSI, the distribution of RC4, and
export controls.
What if you want to post an article which is neither pure science nor
pure politics? Go for talk.politics.crypto. Political discussions are
naturally free-ranging, and can easily include scientific articles. But
sci.crypt is much more limited: it has no room for politics.
It's appropriate to post (or at least cross-post) Clipper discussions to
alt.privacy.clipper, which should become talk.politics.crypto.clipper at
some point.
There are now several PGP newsgroups. Try comp.security.pgp.resources if
you want to find PGP, c.s.pgp.tech if you want to set it up and use it,
and c.s.pgp.discuss for other PGP-related questions.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt. Try alt.security.
Other relevant newsgroups: misc.legal.computing, comp.org.eff.talk,
comp.org.cpsr.talk, alt.politics.org.nsa, comp.patents, sci.math,
comp.compression, comp.security.misc.
Here's the sci.crypt.research charter: ``The discussion of cryptography,
cryptanalysis, and related issues, in a more civilised environment than
is currently provided by sci.crypt.'' If you want to submit something to
the moderators, try [EMAIL PROTECTED]
---Dan
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Compress before Encryption
Date: Sun, 26 Sep 1999 08:20:44 GMT
It has been discussed that many forms of compression would be useful
before encryption is used on a data file. Well I have an adaptive huffman
compression that is one to one. Meaning that if any false key was used
it would uniquely uncompress and recompress back to the false file when
a wrong key is used.
One may wonder of this can be done with static huffman compression where
the structure of the table is sent in a seamless matter with in the first
few several bytes of the file. The anwser is no. Here is a simple proof. First
assume you can do it that make a full pass through the file and you come up
with the optimal table. That you code in the first few bytes of file and then
compress the file. All looks nice no wasted space or information since the
table was so cleverly compressed with some neat method. Know suppose
this compressed file has some exta bytes add to the file. maybe all zero
bytes. Since we want a "one to one" compressor we try to decompress this
file. We do it matches the old file until we get to the long block of zeros.
This decompresses all to the same character since it can be only from the
same token used several times.
But if I try to compress the file when. I make a pass though this particular
file I get a different frequency count than with the shorter file. There fore
I would come up with a different optimal static huffman table. This means
if the table in the front part of file it has to be different so therefor the
static huffman compresion was not one to one. This does not happen
with tha adaptive huffman compression since the table changes each time
a character is read.
This means that a staic huffman compressor or even BTW types of compressors
can never be 'one to one'. So the question is if one uses a bad key to decrypt
a file that was perfectly compressed using static huffman compression
with a perfect compressed table all stored at front of file there is a good
chance the resulting file would not uncompress and recompress back to the
same file. Meaning even with zero knowledge of the file. The compression
then encryption method gives a lot of information to the attacker. IF
one goes to "www.leidich.com/huffman.htm" it tells that even if one is
using a single tree of all 256 bits combinations. Then the number of basic
tree shapes alone is larger than 10^64 this would be greater than 1 in
2^200 so I think it would be a major mistake to use static huffman compression
before you send where the table is optimized for the data being sent.
In other words if your going to use huffman compress use adaptive one to one
or a fixed static one to one where the table is fixed for all messages.
http:/members.xoom.com/ecil/compress.htm
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED]
Subject: Introductory Crypto Site
Date: Sun, 26 Sep 1999 14:37:34 GMT
http://library.advanced.org/28005/
My team, for ThinkQuest, a competition to build educational web sites,
has chosen the topic of Cryptography. We did this after realizing that
there are few sites on the topic for beginners.
We try to cover the history in a readily accessible format, and provide
interactive demonstrations of various algorithms. In addition, we have
a Hall of Fame, where the names of people who can break our cryptograms
go. Another interesting aspect of our site is it's potential for
growth. We have a section for people (like you) to upload interviews
and editorials on encryption, all of which will go online as soon as we
receive them.
Please give us a try. If you're not interested, sorry to bother you.
http://library.advanced.org/28005/
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: peekboo
Date: Sun, 26 Sep 1999 15:48:45 GMT
PeekBoo v1.51 is available from
http://www.cell2000.net/security/peekboo/index.html
What is Peekboo?
It's a free message encryptor for win32 platforms (win95/win98 ...). It
allows users to encrypt/decrypt messages and share public keys in any text
medium (chat, icq, irc, email, usenet).
Features?
- six publicly known symmetric ciphers (blowfish, cast, rc4, rc5, rc6,
twofish) - Diffie-Hellman key exchange (2048 bit modulus) - Simple interface
- Fast - Compact (you can fit the binary and keyring on a floppy in about
60kb). - Source for the ENTIRE program is on the website.
Visit the site for more information, and if you want to test it send me your
public key and a message to [EMAIL PROTECTED] (my public key is on the
page). Or if you have questions you can email me as well.
So far all feedback has been positive. Some people in offices use it so send
secure memos others use it to chat with friends.
Please check it out and give feedback if possible. If you think it's greate
and love using it send me an email I would love to hear from ya. If you
think it sucks and want to tell me go ahead :)
Thanks for the time,
Tom St Denis
-- This is a bimonthly advertisement ---
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Alex Vinokur <[EMAIL PROTECTED]>
Crossposted-To: comcomp.theory,comp.compression,sci.math
Subject: Paul Black's Dictionary of Algorithms and Data Structures
Date: Sun, 26 Sep 1999 12:48:34 GMT
Please visit:
http://hissa.ncsl.nist.gov/~black/CRCDict
I think this site may be of interest to many users.
Alex Vinokur
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Sun, 26 Sep 1999 18:33:50 +0200
From: yoni <[EMAIL PROTECTED]>
Subject: Need advice for encrypting information
I built a random access file Data-Base in java and I wish to encrypt the
information stored in it. I want the information to remain encrypted
untill read from disk, but the indexes won't be encrypted.
Becouse this is a "random access" I can't use stream ciphers (or am I
wrong here ?).
What is the safest solution for this situation ?
Thank you,
Yoni.
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: low diffie-hellman exponent
Date: 26 Sep 1999 18:20:17 GMT
Reply-To: [EMAIL PROTECTED]
On 23 Sep 1999 18:36:13 GMT, DJohn37050 wrote:
>1024 bit DL is about 80 bits of security, 2048 is about 112 bits (3 key triple
>DES) and 3072 is about 128 bits (low AES). This is according to NIST in DSA-2.
>Don Johnson
do you have the same type of comparisaon but with elliptic curves ?
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: Need advice for encrypting information
Date: 26 Sep 1999 18:35:02 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 26 Sep 1999 18:33:50 +0200, yoni wrote:
>I built a random access file Data-Base in java and I wish to encrypt the
>information stored in it. I want the information to remain encrypted
>untill read from disk, but the indexes won't be encrypted.
>Becouse this is a "random access" I can't use stream ciphers (or am I
>wrong here ?).
yes there are stream cypher to do random access. Unfortunatly i don't
remember which one. but they are well known and not hard to find.
i think i saw that 'cryptography applied' by bruce schneier.
>What is the safest solution for this situation ?
one, obvious, is to encipher each record independtly.
probably not the safest but an easy one.
------------------------------
Crossposted-To: alt.security.pgp,comp.security.pgp
From: [EMAIL PROTECTED] (David P Jablon)
Subject: Re: Increasing password security dramatically without making it harder to
Date: Sun, 26 Sep 1999 18:49:32 GMT
In article <[EMAIL PROTECTED]>,
Thomas J. Boschloo <[EMAIL PROTECTED]> wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>Instead of hashing the whole pass phrase, you hash the pass phrase with
>some random data appended. I think I'll patent it! It's a great idea and
>it is funny nobody thought of it before.
Funny indeed. The idea is called "salt".
The issue is where to keep it. You're not going to memorize
it, but it must be combined with the password prior to using it.
======================================================
David P. Jablon
Integrity Sciences, Inc.
[EMAIL PROTECTED]
<http://www.IntegritySciences.com>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Schrodinger's Cat and *really* good compression
Date: Sun, 26 Sep 1999 18:55:36 +0200
Douglas A. Gwyn wrote:
>
> The issue is how the Copenhagen interpretation, wherein the
> state of the cat is in a superposition of |live> & |dead>
> until the human opens the box, could make any sense. Is the
> cat in a state of half-existence? Isn't the cat just as
> good an observer (better actually, because it knows the
> answer before the human)? The whole idea was to point out
> significant problems with the Copenhagen interpretation
> of QM.
That's why I said previously that the experiment is an 'analogy'/
'metapohor' which Schroedinger seemed to choose to employ on grounds
of simplicity for communicating the idea of sort of unknown/undecided
state of quantum theory to the layman. But I think this is a
pedagogical failure.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: steganography
Date: Sun, 26 Sep 1999 18:37:34 +0200
marta wrote:
>
> i'm looking for articles about steganography.
> please mail me links on this e-mail
I have the following in my notes:
http://members.iquest.net/~mrmil/stego.html
http://www.mhv.net/~mgraffam/ce/ce.html
http://www.cl.cam.ac.uk/~mgk25/stirmark.html
http://patriot.net/~johnson/neil/sec.html
http://www.cix.co.uk/~klockstone
Perhaps you should also look at
http://www.cryptography.org
for links.
I have a humble article on a simply implementable steganography method
on my web page.
M. K. Shen
=============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED] (John M. Gamble)
Crossposted-To: sci.math
Subject: Re: Purdue's Large Number
Date: 26 Sep 1999 19:42:28 GMT
In article <7senac$6qm$[EMAIL PROTECTED]>, Bob Silverman <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
> *@spam.ruud.org wrote:
>> Peter Gunn <[EMAIL PROTECTED]> writes:
>>
>> > Bob Silverman wrote:
>> >
>> > > In article <7satdt$p2v$[EMAIL PROTECTED]>,
>> > > [EMAIL PROTECTED] (Dave Rusin) wrote:
>> > > > In article <7samo2$kv4$[EMAIL PROTECTED]>,
>> > > > John M. Gamble <[EMAIL PROTECTED]> wrote:
>> > > > >"The number Purdue needs to factor is
>> > > > >163790195580536623921741301545704495839
>> > > > >239656848327040249837817092396946863513
> .......
>> > > >
>> > > > Typo? Easily found factors of 3, 39341, 46591, 163245571
>> > >
>> > > 3^349 - 1 (this number) was finished a couple of years ago.
>> > >
>> > > Factored means fully factored and not just finding a few small
>> > > factors.
>> >
>> > Far be it for me to argue with a crypto god but,
>> >
>> > 3^349-1 =
>> > 3275803911610732478434826030934089916784\
>> > 7931369665408049967563418479389372702642\
>> > 4083130192984521610839436494151115942891\
>> > 3793814775554594607776743489806125777475\
>> > 8568082
>> >
>> > And it couldnt really have been odd could it? ;-)
>
>Divide out the algebraic factor.
>
>>
>> It's also highly unlikely that 3^349 - 1 has 3 as one of its factors.
>
>(3^349-1)/2 does indeed match to the first dozen or so digits
>with the posted number. If the small factors that were claimed
>to be found really are factors, then it appears that there must be a
>typo in the decimal expansion of the number somewhere.
>
Yes, although i couldn't tell you if it was mine or theirs, since
i no longer have the article. I'm inclined to blame them (of
course) since i went through it digit by digit, but hey, it could
have been me.
-john
February 28 1997: Last day libraries could order catalogue cards
from the Library of Congress.
--
Pursuant to US Code, Title 47, Chapter 5, Subchapter II, '227,
any and all unsolicited commercial E-mail sent to this address
is subject to a download and archival fee in the amount of $500
US. E-mailing denotes acceptance of these terms.
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Need advice for encrypting information
Date: 26 Sep 99 19:37:15 GMT
yoni ([EMAIL PROTECTED]) wrote:
: I built a random access file Data-Base in java and I wish to encrypt the
: information stored in it. I want the information to remain encrypted
: untill read from disk, but the indexes won't be encrypted.
: Becouse this is a "random access" I can't use stream ciphers (or am I
: wrong here ?).
While it would be possible to use a stream cipher, since you would need to
start over at the beginning of each record, many common types of stream
cipher would not work well, or would at least require you to increase the
size of each record by adding a random IV. Or you could use physical disk
position to start from, but that involves inconvenience - and insecurity,
should the contents of your data base be subject to change.
: What is the safest solution for this situation ?
A block cipher.
Using a block cipher in CBC mode, and with the record number used as the
IV, would be a reasonably safe solution. There are other, more elaborate
modes that might be even better; the one used by Matt Blaze for an
encrypted file system is an example.
John Savard
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: low diffie-hellman exponent
Date: Sun, 26 Sep 1999 21:36:50 +0100
jerome <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On 23 Sep 1999 18:36:13 GMT, DJohn37050 wrote:
> >1024 bit DL is about 80 bits of security, 2048 is about 112 bits (3 key
triple
> >DES) and 3072 is about 128 bits (low AES). This is according to NIST in
DSA-2.
> >Don Johnson
>
> do you have the same type of comparisaon but with elliptic curves ?
That's easy. For n-bit AES you need a 2n-bit Elliptic Curve.
--
Mike Scott
=========================================
Fastest is best. MIRACL multiprecision C/C++ library for big number
cryptography
ftp://ftp.compapp.dcu.ie/pub/crypto/miracl.zip
------------------------------
From: Peter Gunn <[EMAIL PROTECTED]>
Subject: Re: SNAKE Web Page
Date: Sun, 26 Sep 1999 21:57:10 +0100
Paul Onions wrote:
> Peter Gunn wrote:
> >
> > Hi,
> >
> > SNAKE, my latest attempt at an authenticating key exchange
> > protocol now has a web page!
> >
> > http://www.smdp.freeserve.co.uk/snake.html
> >
>
> From web page:-
> *******************
> 1) A->B: U, R, g^X1 mod f(1,P,R),
> g^X2 mod f(2,P,R),
> g^X3 mod f(3,P,R), ...
> 2) B->A: S, g^Y1 mod f(1,P,R),
> g^Y2 mod f(2,P,R),
> g^Y3 mod f(3,P,R), ...
>
> K=H(U,R,P,(g^Y1)^X1 mod f(1,P,R),(g^Y2)^X2 mod f(2,P,R),...)
>
> 3) A->B: E[K](S)
>
> 4) B->A: E[K](R)
> *******************
>
> Hello Peter,
>
> Assuming I'm not talking complete rubbish (which happens from
> time to time :-) I can see a couple of attacks here.
No, your attacks look good, the more the merrier :-)
Im currently thinking about how to address these issues, and
welcome any input anyone might have.
>
>
> Both attacks assume an active adversary and that P is a weak
> shared secret that can be searched for easily.
>
> The first is simple (and almost a bit of a cheat!). An adversary
> who can impersonate B can recover the password as follows:-
>
> In step (2) the adversary returns S, g, g, g, ... so that A computes
>
> K=H(U,R,P,g^X1 mod f(1,P,R),g^X2 mod f(2,P,R),...)
>
> then sends E[K](S) to the adversary in step (3).
>
> Since the only secret info not available to the adversary in the
> computation of K is now the password P, he can search over all P
> and confirm the correct one from E[K](S).
>
> Similar attacks hold if the adversary returns 0 or 1 in place of g.
Im wondering if this can be fixed by simply not allowing { 0,1,g }
for g^Y1 mod f(1,P,R) ??
Perhaps not allow any values J such that g^J < Z ??
(Z being the minimum f(1,P,R))
> The second attack is a bit more subtle, and depends on the
> adversary's ability to alter messages in transit and to be able to
> determine if A and B authenticate successfully (e.g. ability to
> see if they abort the protocol or not).
>
> I'm assuming that A and B are using a table of n publicly known
> primes for their moduli (as described on your web page), where the
> moduli are selected by f(k,P,R) = H(k,P,R) mod n.
>
> The attack proceeds as follows:-
>
> The adversary watches step (1), and makes a guess as to which modulus
> was used for one of the exponentiations, f(1,P,R) say, call the guess q.
>
> In step (2) the adversary then substitutes B's value g^Y1 mod f(1,P,R)
> with q - (g^Y1 mod f(1,P,R)). Now the critical observation is that,
> when A computes K, if the adversary was correct with its guess and
> X1 is even then A will compute the same key as it would have done if
> the adversary had not tampered with the message. Thus A and B will
> still authenticate each other. If the adversary sees this then he
> knows with high probability that his guess was correct and so from
> the relationship q = H(1,P,R) mod n he is able to start sieving P.
> With a few successful guesses (and even X1s) he should be able to
> recover P completely.
Here, Im thinking that perhaps if I used...
K=H(U,R,P,
(g^Y1)^X1 mod f(1,P,R),(g^Y2)^X2 mod f(2,P,R),...,
g^X1 mod f(1,P,R),g^X2 mod f(2,P,R),...,
g^Y1 mod f(1,P,R),g^Y2 mod f(2,P,R),...)
(basically throw in the public values for A and B which we have anyway)
...then that might be effective in stopping tampering with the values
supplied??
>
> So there they are. Of course, these attacks as stated are easy to
> thwart with some tweaks to the protocol, but nevertheless are, I think,
> quite illuminating.
Agreed :-) food for thought.
> Also, I'm wondering if the second attack can be generalised in some way.
> But assuming all the primes are of the form 2p+1, then nothing obvious
> springs to mind.
>
> (apart from, if A doesn't check that g^Y1 mod f(1,P,R) is reduced to be
> less than the modulus, then the adversary could substitute the value
> q + g^Y1 mod f(1,P,R) and also now wouldn't need to be lucky with an
> even X1)
Yes, I will have to make sure it is clearly stated what must be checked.
Regards,
PG.
------------------------------
From: Paul Onions <[EMAIL PROTECTED]>
Subject: Re: SNAKE Web Page
Date: Sun, 26 Sep 1999 19:37:48 +0000
Peter Gunn wrote:
>
> Hi,
>
> SNAKE, my latest attempt at an authenticating key exchange
> protocol now has a web page!
>
> http://www.smdp.freeserve.co.uk/snake.html
>
>From web page:-
*******************
1) A->B: U, R, g^X1 mod f(1,P,R),
g^X2 mod f(2,P,R),
g^X3 mod f(3,P,R), ...
2) B->A: S, g^Y1 mod f(1,P,R),
g^Y2 mod f(2,P,R),
g^Y3 mod f(3,P,R), ...
K=H(U,R,P,(g^Y1)^X1 mod f(1,P,R),(g^Y2)^X2 mod f(2,P,R),...)
3) A->B: E[K](S)
4) B->A: E[K](R)
*******************
Hello Peter,
Assuming I'm not talking complete rubbish (which happens from
time to time :-) I can see a couple of attacks here.
Both attacks assume an active adversary and that P is a weak
shared secret that can be searched for easily.
The first is simple (and almost a bit of a cheat!). An adversary
who can impersonate B can recover the password as follows:-
In step (2) the adversary returns S, g, g, g, ... so that A computes
K=H(U,R,P,g^X1 mod f(1,P,R),g^X2 mod f(2,P,R),...)
then sends E[K](S) to the adversary in step (3).
Since the only secret info not available to the adversary in the
computation of K is now the password P, he can search over all P
and confirm the correct one from E[K](S).
Similar attacks hold if the adversary returns 0 or 1 in place of g.
The second attack is a bit more subtle, and depends on the
adversary's ability to alter messages in transit and to be able to
determine if A and B authenticate successfully (e.g. ability to
see if they abort the protocol or not).
I'm assuming that A and B are using a table of n publicly known
primes for their moduli (as described on your web page), where the
moduli are selected by f(k,P,R) = H(k,P,R) mod n.
The attack proceeds as follows:-
The adversary watches step (1), and makes a guess as to which modulus
was used for one of the exponentiations, f(1,P,R) say, call the guess q.
In step (2) the adversary then substitutes B's value g^Y1 mod f(1,P,R)
with q - (g^Y1 mod f(1,P,R)). Now the critical observation is that,
when A computes K, if the adversary was correct with its guess and
X1 is even then A will compute the same key as it would have done if
the adversary had not tampered with the message. Thus A and B will
still authenticate each other. If the adversary sees this then he
knows with high probability that his guess was correct and so from
the relationship q = H(1,P,R) mod n he is able to start sieving P.
With a few successful guesses (and even X1s) he should be able to
recover P completely.
So there they are. Of course, these attacks as stated are easy to
thwart with some tweaks to the protocol, but nevertheless are, I think,
quite illuminating.
Also, I'm wondering if the second attack can be generalised in some way.
But assuming all the primes are of the form 2p+1, then nothing obvious
springs to mind.
(apart from, if A doesn't check that g^Y1 mod f(1,P,R) is reduced to be
less than the modulus, then the adversary could substitute the value
q + g^Y1 mod f(1,P,R) and also now wouldn't need to be lucky with an
even X1)
Regards,
Paul(o)
--
Paul Onions [EMAIL PROTECTED]
PGP 2.6.3 key available
D704688BEFBF2D5D 546BC1D603E2A8E0
------------------------------
** 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
******************************
