RE: Interesting attack to DSA

The newsgroup posting by Vlastimil Klima, one of the Czech researchers
who identified the problems associated with potential modifications to
the secret key file, has now appeared on my local news server.  (He also
sent me a copy personally.)  It also includes the text of the attack
posted to sci.crypt which could work even with mathematical checks of
the consistency of the DSS key.  This attack is far less powerful than
the original Czech attack, which was itself of highly limited impact
IMO. But here are the messages, for future reference:

> From: "Vlastimil Klima" <v(_dot_)klima(_at_)decros(_dot_)cz>
> Newsgroups: sci.crypt
> References: <99jdj9$1n9$1(_at_)news(_dot_)ox(_dot_)ac(_dot_)uk> 
> <3abe252a$1(_at_)news(_dot_)cvut(_dot_)cz> 
> <20010402192001(_dot_)22654(_dot_)qmail(_at_)nym(_dot_)alias(_dot_)net>
> Subject: Re: Is this a solution to the PGP flaw
> Date: Tue, 3 Apr 2001 12:00:10 +0200
> Lines: 68
> Organization: Decros Ltd., ICZ Group, Prague, Czech Republic
> X-Priority: 3
> X-MSMail-Priority: Normal
> X-Newsreader: Microsoft Outlook Express 5.00.2919.6600
> X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6600
> NNTP-Posting-Host: brana.i.cz
> X-Original-NNTP-Posting-Host: brana.i.cz
> Message-ID: <3ac99fb1$1(_at_)news(_dot_)cvut(_dot_)cz>
> X-Trace: 3 Apr 2001 11:02:25 +0100, brana.i.cz
> Path: news.cvut.cz!brana.i.cz
> Xref: news.cvut.cz sci.crypt:151235
>
> Great observation!
>
> In the article "Breaking Public Key Cryptosystems on Tamper Resistance
> Devices in the Presence of Transient Faults" by Bao, Deng, Han,
> Jeng,Narasimhalu and Ngair (Security Protocols, 1997, Springer-Verlag, LNCS
> vol. 1361, pp.115-124) is a very similar idea.
>
> Your attack needs more iterations, but it is very interesting.
>
> In our paper ( http://www.i.cz/en/pdf/openPGP_attack_ENGvktr.pdf), section
> 7, we proposed "temporary tests (say for a patch) " and "future
> countermeasures".  On the temporary tests we said
> "....We stress out that the aforesaid test is not to be a substitute for the
> missing check of integrity of the file with the private key but it is to
> serve as a temporary measure which prevents the herein specified attack..."
> and at section 7.2 we said:
> "...Let us also note that whereas such type of tests as we already mentioned
> is trusted a lot, for instance in RSA, in case of DSA we have to be careful.
> Unlike RSA there is only one value here (private key x), unknown by the
> attacker. Other parameters are known by the attacker and it may change them
> at its own discretion. This is a reason, why this test is considered only a
> temporary solution, which must be replaced as soon as possible with another
> type of check of integrity of the discussed records, as hereafter specified.
> "
>
> Our recommendations are expressed in section 7.4 of the paper.
>
> Vlastimil Klima and Tomas Rosa
>
> "lcs Mixmaster Remailer" <mix(_at_)anon(_dot_)lcs(_dot_)mit(_dot_)edu> wrote 
> in message
> news:20010402192001(_dot_)22654(_dot_)qmail(_at_)nym(_dot_)alias(_dot_)net(_dot_)(_dot_)(_dot_)
> > Here is another variant on the attack which will still work even if
> > the recommended mathematical checks are done.  However it leaks only a
> > small amount of information about the secret key.
> >
> > We have g^q = 1 mod p; g^x = y mod p; q | (p-1), etc.  Now suppose an
> > attacker wants to learn if x is even or odd.
> >
> > He can toggle the low order bit of x by xoring into the ciphertext.
> > As is well known, in CFB mode, such an xor goes through to the
> > plaintext at the cost of disturbing the following block of plaintext.
> > (CBC has similar properties, but with the roles of the two plaintext
> > blocks reversed.)
> >
> > Toggling the low order bit of x will either increment it or decrement
> > it, depending on whether x is even or odd.  This will cause y to be
> > either multiplied by g, or divided by g.
> >
> > The attacker makes a guess about x being even or odd, toggles the bit
> > and adjusts y accordingly.  (He also has to adjust the checksum, which
> > he can do with 50% success.)  The resulting key is perfectly
> > consistent mathematically, if his guess was correct.
> >
> > Then he sees if the user is able to use the key, or if he gets an
> > error.  If there is no error, the attacker knows he guessed right
> > about the low bit of x.
> >
> > In some circumstances it may be possible for the attack to be mounted
> > repeatedly and gradually learn more bits.  For example, if the attack
> > is possible because the key is stored on a network file system, as Dr.
> > Klima proposes, the user may re-run PGP repeatedly when he gets an
> > error, thinking he is typing his passphrase wrong.  In some
> > configurations this will re-fetch the secret key ring each time, and
> > the attacker can modify a different bit of x each time.  He can learn
> > almost 128 bits of x in the best case.  With this advantage, brute
> > forcing the remaining bits of x may be possible.