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

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

Xref: sparky sci.crypt:6542 alt.security.pgp:467
Newsgroups: sci.crypt,alt.security.pgp
Path: sparky!uunet!zaphod.mps.ohio-state.edu!howland.reston.ans.net!usc!sol.ctr.columbia.edu!destroyer!ncar!sage.cgd.ucar.edu!prz
From: [e-mail] (Philip Zimmermann)
Subject: Zimmermann's responses to Sidelnikov's PGP critique
Message-ID: <[e-mail]>
Sender: [e-mail] (USENET Maintenance)
Organization: Climate and Global Dynamics Division/NCAR, Boulder, CO
Date: Fri, 8 Jan 1993 17:37:01 GMT
Lines: 183


This note is in response to criticisms of PGP by Dr. Sidelnikov of
the Moscow State University in Russia, posted on sci.crypt and
alt.security.pgp.

My responses are interspersed with the remarks of Dr. Sidelnikov.


>  About using the electronic signature for protection of
>  commercial information:

>  The analysis of PGP ver.2.0 program.


>        THE MATHEMATICAL CRYPTOGRAPHY PROBLEMS LABORATORY
>
>    The MSU   mathematical   cryptography   problems   laboratory
>employeers with  some  addition  specialists  were  executed  the
>preliminary analysis of PGP ver.2.0 program.
>
>    The preliminary study of  working  and  program  source  code
>analysis result in following PGP features and problems:
>
>    1. The common character problems
>
>    - 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
either case, evidence should be presented that allows others to
reproduce his results.  The random.c code for getting randomness from
keyboard latency has been tested pretty well, and it uses MD5 to
enhance the raw randomness from the keyboard timings.  It looks
pretty good to me.  Does the IDEA cipher running in CFB mode output
text that appears nonrandom?  This is disturbing, if true.  Biham and
Shamir have thus far not succeeded in finding weaknesses in the IDEA
cipher.  Perhaps Dr. Sidelnikov has found one.  I'd like to see some
evidence of this claim.

>    - 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.

>    - 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.


>    2. The RSA algorithm realization problems
>
>    - 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?

>    - 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?


>    3. The electronic signature problems
>
>    - 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?

>    - 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 doubt that RSA or MD5 have weaknesses that have surfaced here.
If PGP has a bug in implementing RSA or MD5, I'd like to see a better
description of the problem, to help find the bug.  Is it possible
to get a more coherent English translation of these remarks?  What is
the evidence of these assertions, so that the results may be reproduced?


>    4. The block encryption algorithm problems
>
>    - 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.

>
>    The conclusions:
>
>    It is recommended to use encryption with 1024 bit key length.
>
>    The using of electronic  signature  is  not  recommended  and
>    requires the additional study.
>
>    The block encryption algorithm has temporary stability.

What does "temporary stability" mean?

>
>    The hashing function  should  be  reduce  in conformity with ISO
>    recommendations.
>
>    The using of PGP program in actual version is undesired.
>
>
>                       The MSU mathematical cryptography
>                       problems Laboratory Manager
>                       Academician
>
>                          Dr. Sidelnikov V.M.


In conclusion, I'd like to point out that normally, when an academic
paper is published that claims a cryptosystem is weak, it generally
includes some real data to back up its claims.  Such data is
conspicuously absent here.

There have been some programming bugs in PGP.  Some of these bugs are
found by the user community.  When they have been found, they have
been fixed.  PGP 2.1 has numerous bug fixes over version 2.0.  There
are also some known bugs in 2.1, as were recently discovered by Juha
Sarlin.  But I am not aware of any extant bugs or bugs that were in
2.0 that could cause the symptoms described above, at least for the
passages I can understand.  I would certainly welcome some
clarification of these claims to help discover if there are any real
weaknesses in PGP.


Philip Zimmermann