21 March 2001

Source: http://www.icz.cz/en/onas/tisk4.html [Thanks to MO.]

Press Release

Prague, 20.3.2001

Cryptologists from Czech company ICZ detected serious security vulnerability of an international magnitude

A bug has been found in worldwide used security format OpenPGP. The bug can lead to discovery of user's private keys used in digital signature systems. OpenPGP format is widely used in many applications used worldwide, including extremely popular programs like PGP^TM, GNU Privacy Guard, and others. The bug detection comes on the right time, as Philip Zimmermann, the creator of PGP program, has left Network Associates, Inc. and aims to boost OpenPGP format in other products for privacy security on Internet. From the scientific point of view, the discovery goes far beyond actual programs - it has wider theoretical and practical impact.

Two Czech cryptologists, Vlastimil Klima and Tomas Rosa, from a company Decros (member of ICZ group) detected insufficient security protection of private signature keys while working on a research for the Czech National Security Authority. The private signature key is the most sensitive and therefore the most protected information in all digital signature systems. The attack is described in detail in a research report to be released shortly on Internet (http://www.i.cz) in both Czech and English.

The attack on OpenPGP format leading to discovery of DSA and RSA private signature keys is described in the research report. OpenPGP format is being proposed as an Internet standard for exact definition of content and meaning of data records, in relation to encryption and to digital signature.

This format is used not only in groups of programs called PGP^TM, but also in other applications, including GNU Privacy Guard. The list of products based on OpenPGP is available on Internet at http://www.pgpi.org/products. OpenPGP format and all the applications need to be reviewed the same way as the PGP^TM program itself.

The attack was successfully verified and demonstrated on PGP^TM(*) version 7.0.3 using AES and DH/DSS algorithms, which are deservedly being considered as highly secure.

This serious bug is caused by incorrect implementation of the above-mentioned strong cryptographic techniques. The private signature key is the basic and the most sensitive information in the whole system. The user is using it for digital signature. In all systems, including OpenPGP, it is therefore protected by a strong cipher. AES, one of the latest strong algorithms, has been used in the attacked system. However, the protection appears to be illusory.

The authors proved that attackers do not need to attack the strong cipher itself. They can simply bypass it as well as the secret user's passphrase. A slight modification of the private key file followed by capturing a signed message is enough to break the private key. These tasks can be performed without knowledge of the user's passphrase. After that, a special program can be run on any office PC. Based on the captured message, the program is able to calculate the user's private key in half a second. The attacker can then sign any messages instead of the attacked user. Despite of very quick calculation, the program is based on a special cryptographic know-how.

Insufficient security of public and private parts of signature keys in OpenPGP format has been analyzed for DSA and RSA algorithms. The step-by-step description of the attack on both private signature keys is being demonstrated. The attacks apply to all RSA and DSA parameter lengths (modules, keys).

The demonstrated attacks have a strong impact on security of the programs mentioned above. To complete the attack, it is not always necessary to visit the attacked user's workstation. The vulnerability of the system is also in the files with exported private keys used by the user for transferring the keys between workstations. The fact that the private key is stored in an encrypted form can cause an illusory feeling of security. If this file or diskette is captured by an attacker during the transfer, the security of user's private key is in serious danger.

We can often see that users store private key files on shared devices on a network to maintain easy access. Knowing that the key is protected by a strong cipher, the user considers such storage to be safe enough. The authors proved that this feeling is illusory. Typically, the server administrator can be the attacker.

Knowing the details of the demonstrated attack, the user of programs based on OpenPGP is in a difficult situation when he/she realizes that an invalid signature value has been generated. The user cannot be sure whether this happened because of the attack, or 'just' because of a technical failure. It is obvious that every file with an invalid signature has to be handled carefully, the same way as a file with the private key in open form! This includes careful secure wiping of the file from the workstation or the server.

The completed analysis of the OpenPGP format has discovered serious defects that make OpenPGP based applications vulnerable. The practical example is PGP^TM program which is not resistant to the attack on DSA algorithm. However, the program is resistant to the attack on RSA algorithm because of additional protections beyond OpenPGP format.

Though the attack relates to RSA and DSA algorithms in OpenPGP, similar vulnerabilities can be expected in other asymmetrical cryptographic systems, including systems based on elliptic curves. OpenPGP format and PGP^TM program are likely not the only examples of systems that can be attacked because of insufficient protection of the parameters mentioned above. In the end of their research report, the authors propose cryptographic measures correcting OpenPGP format and PGP^TM program as well. They strongly appeal for very careful design of cryptographic systems.

The New York Times, March 21, 2001

Cryptologists Discover Flaw in E-Mail Security Program

By JAMES GLANZ

Two cryptologists announced yesterday that they had found a flaw in the most widely used program for sending encrypted, or coded, e-mail messages. If confirmed, the flaw would allow a determined adversary to obtain secret codes used by senders of encrypted e-mail.

The program, called P.G.P. for Pretty Good Privacy, is used by human rights organizations to protect vulnerable sources, by corporations to ensure secure communications and by millions of individual users. American security experts cautioned that they could not fully judge the accuracy of the claim, which was issued in Prague, before more technical details become available. The experts also noted that some sort of access to the sender's computer — either directly or via the Internet — would be needed to exploit any such flaw.

According to a statement issued yesterday by ICZ, an information technology company in Prague with about 500 employees, the cryptologists, Vlastimil Klima and Tomas Rosa, found the problem while doing research on secure communications for the Czech government.

"It is very serious," said Kriz Zdenek, general manager of ICZ, adding that a technical paper on the finding would be made available by Friday on the company's Web site (www.icz.cz/).

Mark McArdle, vice president of P.G.P. engineering at Network Associates in Santa Clara, Calif., which licenses the encryption program to corporate and individual users, said he had already assigned a team of engineers to check out the claim, which he learned of yesterday from a journalist.

"We are very eager to both analyze this and respond to it," Mr. McArdle said. "We want to make sure that our systems are completely robust."

He expressed surprise that the Czech company did not inform him of the problem so that a software fix, often called a patch, could be made available with the announcement of any bug. But Miroslav Votruba, marketing director at ICZ, said several e- mail messages informing Network Associates of the problem more than a week ago received no response.

"We are willing to cooperate before the algorithm or description of the problem will be released on the Web," Mr. Votruba said.

P.G.P. relies on a type of cryptography that uses two separate keys, one to encode a message and one to decode it. The flaw claimed by the cryptographers does not involve cracking the code itself, which is considered virtually invulnerable, but would work around it by allowing an intruder to steal one of the keys held privately by a user.

Without such a flaw or bug, the private key would be unavailable even to an intruder who gained access to a computer, because it exists there only in scrambled form. The ICZ announcement says there is a way to unscramble it but gives few details. Mr. McArdle said such a bug would mainly affect the coded electronic "signatures" that allow the recipient to verify the sender's identity. In effect, it would allow the intruder to impersonate the sender in future communications.

"This is probably real," said Bruce Schneier, founder and chief technology officer of Counterpane Internet Security in San Jose, Calif., referring to the bug. But he said it showed that e-mail security involved more than simply protecting the message in transit on the Internet.

Dr. Michael A. Caloyannides, a senior fellow at Mitretek Systems in McLean, Va., said the bug would be "a bit of a shock," since P.G.P. had been considered essentially invulnerable. And Matthew Zimmerman, project coordinator for the Science and Human Rights Program of the American Association for the Advancement of Science, confirmed that his organization routinely used P.G.P. to protect dissidents and informers around the world.

But even if the problem does turn out to be serious, said Jonathan Zuck, president of the Association for Competitive Technology in Washington, an industry group involving information technology, security-conscious Internet users should not panic.

"This kind of technology arms race is always a factor in any new technology standard," Mr. Zuck said, adding that the eventual result should be an improved encryption program.

Date: Wed, 21 Mar 2001 09:36:57 +0000
From: Ken Brown <k.brown@ccs.bbk.ac.uk>
To: cypherpunks@cyberpass.net
Subject: [Fwd: Have they found a serious PGP vulnerability?!]

Forwarded without permission from BUGTRAQ. I have no idea if there is any substance in the rumour,  though I imagine there probably isn't.

Ken Brown

Pavel Kankovsky wrote:

The rumour goes around that a group of cryptologists working for a Czech company called ICZ has discovered a fatal problem in PGP as a side effect of their work on a special crypto device for the Czech government.

If you understand Czech (or if you want to check all the keywords are there), you can read an article titled "Do you trust PGP? A mistake!" about the whole thing at http://www.swnet.cz/article.php?id=15096

Allegedly, there is a vulnerability in OpenPGP format definition (sic) > allowing an attacker to circumvent (sic) the encryption used to protect private signing keys and to recover those keys in real time (sic).

To make the article sound a little more like a piece of FUD, they add that only higher and more demanding professional systems (sic), when implemented and used correctly, can be considered really secure.

No details are available right now and the data included in the article seems to be partially self-contradicting (on the other hand, it can be just a result of standard journalistic post-production). They say there will be a press conference today (March 20) at 15:00 MET where ICZ people will shed more light on this issue.

Personally, I think they have found some new obscure attack (perhaps some side-channel attack) that can be used when some bizzare conditions are met, or maybe they have reinvented the wheel, and have discovered a Trojan horse can steal private keys when PGP decrypts them in order to be able to use them.

--Pavel Kankovsky aka Peak  [ Boycott Microsoft--http://www.vcnet.com/bms ]

"Resistance is futile. Open your source code and prepare for assimilation."

http://www.wired.com/news/politics/0,1283,42553,00.html

   Your E-Hancock Can Be Forged
   by Declan McCullagh (declan@wired.com)
   10:20 a.m. Mar. 21, 2001 PST

   WASHINGTON -- A Czech information security firm has found a flaw in
   Pretty Good Privacy that permits digital signatures to be forged in
   some situations.

   Phil Zimmermann, the PGP inventor who's now the director of the
   OpenPGP Consortium, said on Wednesday that he and a Network Associates
   (NETA) engineer verified that the vulnerability exists.

   ICZ, a Prague company with 450 employees, said that two of its
   cryptologists unearthed a bug in the OpenPGP format that allows an
   adversary who breaks into your computer to forge your e-mail
   signature.  

   Both Zimmermann and the Czech engineers, Vlastimil Klima and Tomas
   Rosa, point out that the glitch does not affect messages encrypted
   with PGP. OpenPGP programs -- including GNU Privacy Guard and newer
   versions of PGP -- use different algorithms for signing and
   scrambling, and only the digital signature method is at risk.  

   PGP and its offspring are by far the most popular e-mail encryption
   programs in the world. Nobody has disclosed a flaw in their
   message-scrambling mechanisms, but PGP owner Network Associates
   suffered an embarrassment last August when a German cryptanalyst
   published a way that allows  an attacker to hoodwink PGP into not
   encoding secret information properly.

   In this case, someone wishing to impersonate you would need to gain
   access to your secret key -- usually stored on a hard drive or a
   floppy disk -- surreptitiously modify it, then obtain a message you
   signed using the altered secret key. Once those steps are complete,
   that person could then digitally sign messages using your name.

   "PGP or any program based on the OpenPGP format that does not have any
   extra integrity check will not recognize such modification and it will
   allow you to sign a message with the corrupted key," says Rosa, who
   works at Decros, an ICZ company. Rosa says he demonstrated the
   vulnerability with PGP 7.0.3.

   [...]

To: cypherpunks@sirius.infonex.com
From: iang@cs.berkeley.edu (Ian Goldberg)
Subject: Re: PGP flaw found by Czech firm allows dig sig to be forged
Date: 21 Mar 2001 22:00:27 GMT

In article <20010321133551.B2386@cluebot.com>,
Declan McCullagh  <declan@well.com> wrote:
>
>
>http://www.wired.com/news/politics/0,1283,42553,00.html
>   
>   Your E-Hancock Can Be Forged
>   by Declan McCullagh (declan@wired.com)
>   10:20 a.m. Mar. 21, 2001 PST
   

Of course, if someone can modify your private keyring, I'd suspect your
TCB is toast.  (Unless you're in the habit of shipping your private keyring
around the Internet.)

For the interested, this is my guess at the attack.

Modify the encrypted value of p, somewhere near the middle.
When decrypted, depending on the chaining mode, it's possible that
only a couple of blocks of p will be mangled, and the remainder
of the private key file will decrypt successfully.  Here's where
PGP fails to do a MAC to verify integrity of the data.

Then, it behaves just like DFA (Differential Fault Analysis).
The idea is that to calculate a signature M^d mod n, we calculate
M^d mod p and M^d mod q, and use the CRT to combine them to S = M^d mod n.

If p is wrong, the result S' will be correct mod q but incorrect mod p.
so S' ^ e mod q = M mod q, but S' ^ e mod p != M mod p.

Therefore GCD(S' ^ e mod n, M) = q, and we're done.

   - Ian



To: cypherpunks@sirius.infonex.com
From: nikitab@cs.berkeley.edu (Nikita Borisov)
Subject: Re: PGP flaw found by Czech firm allows dig sig to be forged
Date: 21 Mar 2001 22:27:04 GMT

In article <99b89r$lgd$1@abraham.cs.berkeley.edu>,
Ian Goldberg <iang@cs.berkeley.edu> wrote:
>If p is wrong, the result S' will be correct mod q but incorrect mod p.
>so S' ^ e mod q = M mod q, but S' ^ e mod p != M mod p.
>
>Therefore GCD(S' ^ e mod n, M) = q, and we're done.

I think you meant GCD((S'^e mod n)-M, n) = q.  I don't think what you
said is true, since q does not necessarily divide M.

- Nikita