NetNews Usenet Archive 1993 #1/NN_1993_1.iso/spool/sci/crypt/6549

Internet Message Format | 1993-01-08 | 10.1 KB

Xref: sparky sci.crypt:6549 alt.security.pgp:470
Newsgroups: sci.crypt,alt.security.pgp
Path: sparky!uunet!paladin.american.edu!howland.reston.ans.net!usc!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!Sirius.dfn.de!news.DKRZ-Hamburg.DE!rzsun2.informatik.uni-hamburg.de!fbihh!bontchev
From: [e-mail] (Vesselin Bontchev)
Subject: Re: Zimmermann's responses to Sidelnikov's PGP critique
Message-ID: <bontchev.726522074@fbihh>
Sender: [e-mail] (Mr. News)
Reply-To: [e-mail]
Organization: Virus Test Center, University of Hamburg
References: <[e-mail]>
Date:  8 Jan 93 19:41:14 GMT
Lines: 193

[e-mail] (Philip Zimmermann) writes:

> >    - the  sequence  of  random numbers has strong prevalences on
> >bytes (up to 0.05 ...  0.1 on material of 10000 byte) and  strong
> >correlation dependence between contiguous bytes;

> Really?  How so?  What does "strong prevalences" mean?  Is he talking
> about the internal random number source in random.c, used for making
> RSA keys?  Or is he talking about the output of the IDEA cipher?  In

Seems that he is talking about random.c. I think we saw here another
message that described a patch how to make it "more random". What
Sidelnikov probably means is that if you generate a lot of random
numbers with the random number generator, they do not look random
enough to him - e.g., there is a corelation of 0.05 to 0.1 between the
bytes in a 10,000-byte sample. We should try to generate a lot of
random numbers and verify whether it is indeed so...

> either case, evidence should be presented that allows others to
> reproduce his results.  The random.c code for getting randomness from

Uh, what kind of evidence? A sample of 10,000 random bytes?

> >    - the program doesn't check it's own integrity,  so it can be
> >infected by "virus"  which  intercept  confidential   keys   and
> >passwords used for  their protection and save them onto magnetic
> >carriers;

> The PGP manual warns of this problem.  A well-designed virus could
> defeat any self-checking logic by attacking the self-checking logic.
> It would create a false sense of security if PGP claimed to check
> itself for viruses when you run it.

It is strange that a Russian does not know that self-checking programs
can be easily fooled (at least in MS-DOS) by stealth viruses... There
are enough stealth viruses known (and some even made) in Russia...

But maybe he means that a self check will help catch at least the
simple (i.e., non-stealth) viruses. This is true, but there is another
problem. Since the program is designed to be portable, obviously its
checksum cannot be hard-coded in it - because it will be different
when you compile the program on a different platform or even with a
different compiler. Therefore, the only way to add self-checking
capabilities to it is to run an external program on the compiled
executable that computes the checksum (say, MD5) of the file and
stores it somewhere in the executable, which is marked somehow.
Unfortunately, in order to keep the portability, this program has also
to be published in source and the "marker" of the place where the
checksum is stored must be also made public. Not to speak that the
checksum algorithm must be also well-known. In this case, it becomes
trivial to modify (e.g., infect) the executable, then compute its new
checksum, locate the place where it is stored and patch it to the new
value. As you mentioned, such direct attack is always possible (i.e.,
even if the checksum algorithm is not well known and the place where
the checksum is stored is not publicised), but with the source
available the attack becomes just trivial. No, there is really no
point to make PGP check itself. The most one can do is to distribute a
detached signature of the files in the archive. This is currently done
with the MS-DOS executable, but maybe it should be done with the
source files too...

> >    - the program has not  optimal  exponentiation  algorithm  in
> >GF(P) field,   when  P  -  prime  number,  which  result  in  low
> >performance;

> PGP is freeware.  Maybe the exponentiation is not as optimal as it
> could be if the PGP development effort were funded.  In any case,
> improvements in the math algorithms have made PGP 2.0 faster than
> version 1.0, and version 2.1 is faster still.  Of course, suggestions
> for improving the performance of the algorithms are always welcome.

I think we have seen another comment on that... Was it by Robert
Silverman? He is an expert in number theory and factoring, so he
should be the most competent person to comment...

> >    - the prime numbers reception using in this program (R and  q
> >in RSA  algorithm)  permits  not less than on two order to reduce
> >the labour-intensiveness of factorization;  with 256 bit blocks
> >of  data lenght it is possible to execute the cryptanalysis in
> >real time;

> I don't know what this means.  PGP does not normally work with RSA
> keys as small as 256 bits.  No claims are made that this is a safe
> key length.  Larger RSA keys are specifically recommended in the
> manual.  And what does "real time" mean in this case?

Either he has found a bug in the RSA implementation or he just does
not understand the algorithm... :-)

> >    - before using RSA the program executes compression and block
> >encryption that  positively  affects  on  the  common   stability
> >encryption.

> What does this mean, in English?  It sounds like a positive remark,
> not a criticism.  Is a better English translation available?

I am able to understand Russian perfectly, although I cannot speak it
that well. I also have the necessary utilities to display Russian text
on my screen (well, after some hacking - after converting the
character set of the Russian Cyrillics to Bulgarian Cirillics, because
we are using different encoding schemes for the Cyrillic letters). If
the person who has forwarded Dr. Sidelnikov's message could provide me
a reliable e-mail contact with him, I could try to understand what he
means and to post it here...

> >    - for  signature  calculation the program originally executes
> >hashing of file into number of given  length  (256, 512 or 1024 bit),
> >but hashing function does not corresponds the ISO recommendations;

> The MD5 hash used in PGP is widely respected in the crypto community.
> Not conforming to some particular ISO specification does not imply the
> hash function is weak.  The MD5 hash is used in certain other crypto
> standards-- so why should the ISO standard be somehow better than other
> crypto standards?

Either he has never heard about MD5, or he is somehow not happy with
the block length of the hashed blocks... Would be nice if he posts the
particular ISO recomendations he has mentioned...

> >    - when considering the hashing function as the automatic  device
> >without output,  it  is  enough  simply possible to construct the
> >image of reverse automatic device and with using  the  blanks  in
> >text files  (or  free fields in some standard formats as in DBF),
> >to  compensate  the  hashing function  at  changed  file  to  former
> >significance.

> >    Thus, it  is  possible  to  forge  the  electronic  signature
> >without analysis of RSA algorithm.

> How?  This claim sounds alarming, if true.  But it requires that one
> of the following be true:

>  a)  The RSA algorithm itself has a weakness.
>  b)  The MD5 hash algorithm has a weakness.
>  c)  PGP has a programming bug in implementing either RSA or MD5.

I think that he means b). He probably means that he is able to forge
it, which would be understandable if he has never heard of it... :-)

> >    - when executing analysis on  plaintext  and  ciphertext  the
> >linear correlation  dependences  with encryption key were founded
> >(0.01 and more degree);
> >
> >    - also the effective method  of  decreasing security which
> >reduces the  order  of  time  necessery  to key definition in two
> >times in comparison with exhaustive search of all keys  (i.e.
> >algorithm has the labour-intensiveness which is equal the root
> >square from labour-intensiveness of the exhaustive search algorithm)
> >have been found.

> Again, a better English translation is required to decipher this
> claim.  Also, where is the evidence?  This sounds like he's saying
> the IDEA cipher is weak.  Or maybe PGP has a bug in implementing it.
> If so, it should be fixed.  But more information is needed to help
> reproduce the problem, if indeed there is a problem.

He is saying (I think) that the output of the IDEA is not completely
random - like if it doesn't change very much if you change a single
bit of the key. I would be very curious to see how does he compute his
"correlations"... Also, he is mentioning for the second time that
there is a problem in the RSA implementation that allows you to reduce
the time to factor the key to the square root of the number of tries,
if you just try all possible factors (brute force). But he doesn't
explain -how- this can be done and -why- it can be done...

> >    The block encryption algorithm has temporary stability.

> What does "temporary stability" mean?

Maybe he means that a single bit change in the plain text does not
change the cyphertext considerably? Strange...

> >                       The MSU mathematical cryptography
> >                       problems Laboratory Manager
> >                       Academician

This is probably translated incorrectly too... "Academician" is the
highest academical degree in Russia (and many other East European
countries, including Bulgaria) and I sincerely doubt that an
academician will be just a "laboratory manager" and will play with
PGP... He would be much more likely to be a director of an
institute...

I would really like to sort that out. Could the person who forwarded
the message provide me contact with Dr. Sidelnikov?

Regards,
Vesselin
--
Vesselin Vladimirov Bontchev          Virus Test Center, University of Hamburg
Tel.:[phone], Fax: [phone]      Fachbereich Informatik - AGN
< PGP 2.1 public key available on request. > Vogt-Koelln-Strasse 30, rm. 107 C
e-mail: [e-mail]    D-2000 Hamburg 54, Germany