🚀 go-pugleaf

My purpose in posting this is not to enter into the dispute between
Zimmermann and Sidelnikov, but to comment on some interesting questions that
the Sidelnikov post may raise. Some preface may be in order:

In my many individual visits to the Soviet Union at the personal
invitation of the Soviet Academy of Sciences, and in my discussions
with Soviet scientific leaders, it became clear to me that in the
Soviet structure, the academic and Academy scientific structure was
intimately bound up with the military and intelligence structure.
Through the mechanism of the State Committee on Science and Technology
the Soviets ran their Nuclear, Missile, and many other programs.
Leaders in the State Committee were also leaders in the Soviet Academy
of Sciences and in the academic community.

This raises the question of whether Sidelnikov had some senior role,
directly or indirectly, in the Soviet's equivalent of the NSA. If he
did, then his comments may be both authoritative with respect to
access to what once was highly classified technology in the USSR,
and (by the argument of parallelism) revelatory of the state of
technology at the NSA.

In article <1993Jan8.173701.8858@ncar.ucar.edu> prz@sage.cgd.ucar.edu (Philip Zimmermann) writes:
>
>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.

Is this lab a former part of the Soviet NSA? If so, one may assume
a very high level of expertise, which gives major weight to what
Sidelnikov says. We know that many intelligence specialists in
Russia are now under- or unemployed and looking for work in
the Western community. Thus it would not be surprising for Sidelnikov
to "go public" as it were.

>>
>>    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;
>
>Biham and
>Shamir have thus far not succeeded in finding weaknesses in the IDEA
>cipher.  Perhaps Dr. Sidelnikov has found one.>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.

Maybe Sidelnikov is trying to tell us something here that goes beyond
the theoretical.

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

Is Sidelnikov saying more than that the exponentiation isn't as fast
as possible? Is he, perhaps, saying something about cryptographic
weakness?

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

If Sidelnikov says real time, he means real time. I take this to mean
that the Russians, and the NSA can do the factorization and read RSA
traffic with 256 bit keys in real time. If NSA's technology is better
than the Russians, maybe they can read even longer key traffic so
quickly as to make no difference. It would be interesting to see a
calculation (Phil?) which, assuming 256 bit keys can be read in real
time (call it a difficulty factor of 1.0), presents the difficulty
factors for 512 and 1024 bit keys.

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

This attitude is a hiding behind "academic" practice in an area where
Sidelnikov has raised the most serious doubts about a number of
aspects of PGP as presently implemented. For him to be both an
Academician (the highest rank in Soviet Science, given to very few,
and after massive and extended demonstrations of competence) and a
Laboratory Manager means we ought to take his words with at least as
much seriousness (but without the associated "special pleading" doubts
some might have) as similar words from the head of the cryptanalysis
division (or whatever it is called) of the NSA.

Let me be perfectly clear here. Sidelnikov's standing in the
cryptology field in the Soviet scientific community is of the most
senior level, and that's not a statement about science politics. It's
also likely he was (is?) either one of the most senior scientists in the
former KGB cryptanalysis activity, or one of their most senior
advisors.

It's inappropriate to take his remarks as if they were those of some
competitive programmer picking nits about PGP's program code.  It's
especially inappropriate to take a confrontational attitude. I suggest
Phil rethink this. I also suggest that Sidelnikov's advice about the
use of PGP be heeded. Were I going to use it, I'd use no less than a
1024 bit key, and even then worry about some of the other weaknesses.

Finally, I'd suggest extreme politeness in responding to Sidelnikov,
and no little respect. Think of him as the Russian equivalent of
Einstein in his field if it will help. In Soviet Science, Academicians
are analogous to "the immortals".

David

-- 
David Sternlight
RIPEM Public Key on server  --  Consider it an envelope for your e-mail