Bodo Moeller predicted the 512-bit export attacks in TLS in 1998

Bodo Moeller predicted the 512-bit export factoring attacks in TLS in 1998. Since TLS mailing list archives from this time period are hard to find now (I had to use http://web.archive.org/web/20081014015810/http://www.imc.org/ietf-tls/entire-arch.txt), here is one message:

From bounce-ietf-tls-435@lists.consensus.com  Tue Jan 26 18:34:02 1999
Received: from hamlet.consensus.com (hamlet.consensus.com [157.22.240.90])
 by mail.proper.com (8.8.8/8.8.5) with SMTP id SAA20285
 for <ietf-tls-archive@imc.org>; Tue, 26 Jan 1999 18:33:58 -0800 (PST)
Message-Id: <m105KoS-0003bDC@ulf.mali.sub.org>
Date: Wed, 27 Jan 99 03:34 +0100
From: Bodo_Moeller@public.uni-hamburg.de (Bodo Moeller)
To: "IETF Transport Layer Security WG" <ietf-tls@lists.consensus.com>
Subject: Re: RFC 2246
In-Reply-To: <008f01be4976$855fa8c0$3508000a@haruspex>
Organization: Hamburg University
List-Unsubscribe: <mailto:leave-ietf-tls-435N@lists.consensus.com>
List-Software: Lyris Server version 3.0
List-Subscribe: <mailto:subscribe-ietf-tls@lists.consensus.com>
List-Owner: <mailto:owner-ietf-tls@lists.consensus.com>
X-List-Host: Consensus Development Corp <http://www.consensus.com/>
Reply-To: "IETF Transport Layer Security WG" <ietf-tls@lists.consensus.com>
Sender: bounce-ietf-tls-435@lists.consensus.com
X-Lyris-Message-Id: <LYR435-4064-1999.01.26-18.37.52--ietf-tls-archive#imc.org@lists.consensus.com>
Precedence: bulk
X-List-Host: SKYLIST.net <http://www.SKYLIST.net/>

"Tim Dierks" <timd@consensus.com>:

> I don't know if this is final yet: I'm still going over a couple of textual
> nits with the RFC editor. I'd expect it today or tomorrow, though.

It seems that a few days ago somebody fixed the mailing list
administration software for ietf-tls, finally allowing me to subscribe
(after various futile attempts from this and other accounts starting
October 1998 plus an inquiry or two to the administrative address
without any reaction whatsoever).  Congratulations on that.

As already noted in my message of 1998-10-10 to ietf-tls@consensus.com
(rejected because "Only members of ietf-tls are allowed to contribute
messages" although on 1998-10-06, in response to one of my
subscription attempts, I had received a message from
lyris@lists.consensus.com which claimed that "It's a good idea to save
this message somewhere safe so you know how to unsubscribe") and to
TimD@consensus.com, the SSL 3.0 and TLS 1.0 protocols have an
unnecessary weakness which could be used by an attacker to force a
SSL/TLS connection to use weak cryptography even if both systems
support strong cryptography; an edited quote from my old message (all
edits are marked by brackets):

  From: Bodo_Moeller@public.uni-hamburg.de (Bodo Moeller)
  To: ietf-tls@consensus.com
  Cc: TimD@consensus.com
  Subject: Export-PKC attacks on SSL 3.0/TLS 1.0
  Date: Sat, 10 Oct 1998 11:37:42 -0700
  
  I finally found time to read the SSL 3.0 and TLS 1.0 specifications[1],
  and I noticed that there apparently is a potential weakness in those
  protocols.  The scenario to which the attack applies is when both
  client and server are able to perform strong cryptography (i.e., not
  export-weakened), but both are also willing to put up with export
  ciphers if the respective other side does not support strong
  cryptography.

  [Footnote 1 omitted.]

  [...]        All authentication in the protocol relies on the security
  of the algorithms negotiated at [early handshake] stage.  Now assume
  a very strong
  attacker whose equipment and algorithmic know-how allows him to
  decrypt messages encrypted for weak public keys, e.g. by factoring a
  512 bit RSA modulus during its lifetime.  (One might argue that likely
  No Such Attacker exists, but better safe than sorry.)
  
  If the server offers the RSA_EXPORT key exchange method with a 512 bit
  public key, obviously there is no security against this attacker: The
  attacker deletes the strong methods from the cipher suite list in the
  ClientHello message, the server then presents its weak certificate,
  the client sends the weakly encrypted premaster secret across the
  network, the attacker obtains the premaster secret and uses it to
  "authenticate" to both parties.
  
  Thus, the server should not use RSA_EXPORT with 512 bit public keys.
  Fortunately, there are other exportable key exchange method that
  include strong signatures: In the case of RSA_EXPORT with a 1024 bit
  public key, this strong public key can be used to sign a temporary 512
  bit RSA key (Appendix D.1 gives recommendations on how often this
  temporary key should be changed), which is then used to encrypt the
  premaster secret.  Unfortunately, the strong authentication provided
  by the 1024 bit RSA key is not used properly to thwart the attack
  described above: The signature covers, besides the temporary key, only
  the nonces ClientHello.random and ServerHello.random.  This binds the
  temporary key to the current connection, but that is not enough:
  The signature also needs to cover ClientHello.cipher_suites (and, in
  order to be prepared for future protocol changes, also
  ClientHello.client_version).  Only then, there is strong
  authentication for _why_ the server chose an export-weakened cipher.
  
  I did not find this attack mentioned in the David Wagner and Bruce
  Schneier's paper "Analysis of the SSL 3.0 protocol" (November
  19, 1996).  They have a section on "Key-exchange algorithm rollback",
  but their attack is about relabeling Diffie-Hellman parameters as RSA
  parameters (the strong signature should also cover a label that
  explicitly says which key exchange method the server picked).
  
  While I'd bet I am not the first one to notice the weakness pointed
  out above, it obviously has not been dealt with in the TLS protocol
  draft.  The draft should point out that a strong server that offers
  export-weakened [cipher suites] could be forced, by a sufficiently strong
  attacker, to use weak algorithms even if the client also supports
  strong cryptography.  The protocol should be improved by protecting
  more data (as detailed above) with _strong_ authentication in
  ServerKeyExchange messages, so that strong assurance can be achieved
  that the parties will choose the highest strength of cryptography
  supported by both.
  
  Unfortunately, this protocol improvement will be useless until all
  earlier version of the protocol are phased out -- otherwise, the
  attacker can simply change the version number fields and proceed as
  described above.  But there is likely some time until 512 bit
  factoring machines hit the mass market :-)

Later observations on the protocol drafts (quoted from a message which
I mailed on 1998-11-22 to a different list because this one still was
closed) include

              [...] that the draft excludes strong temporary RSA keys
  unless the public key in the certificate "cannot be used for
  encryption" (appendix D.1) -- i.e., strong temporary parameters either
  must be DHE parameters, or the server certificate must have keyUsage
  restricted accordingly.  For some reason, the TLS drafts do not allow
  strong-crypto forward secrecy for RSA-only implementations unless the
  CA put a "keyUsage" extension in the server's X.509 certificate that
  ensures that the key "cannot be used for encryption". -- Maybe the
  draft authors were not even thinking of "keyUsage" restrictions --
  they talk of "X509v3" certificates, but the references list the
  prehistoric 1988 version of X.509 -- i.e., X.509 v1.

The drafts don't even mention forward secrecy, while it is a
subject that definitely ought to be explained in the security
considerations section.

Finally, the definitions of ASN.1Cert and certificate_list have
discrepancies between section 7.4.2 and appendix A.4.2.  The former
are correct:

       opaque ASN.1Cert<1..2^24-1>;

       struct {
           ASN.1Cert certificate_list<0..2^24-1>;
       } Certificate;

The latter, reproduced below, are not -- not that "opaque
ASN.1Cert<2^24-1>" does not even match the "T T'<floor..ceiling>"
syntax defined in section 4.3.

    opaque ASN.1Cert<2^24-1>;

    struct {
        ASN.1Cert certificate_list<1..2^24-1>;
    } Certificate;


Bodo M"oller
<bmoeller@acm.org>

---
You are currently subscribed to ietf-tls as: [ietf-tls-archive@imc.org]
To unsubscribe, forward this message to leave-ietf-tls-435N@lists.consensus.com

Another message:

From bounce-ietf-tls-435@lists.consensus.com  Tue Feb  2 02:24:50 1999
Received: from hamlet.consensus.com (hamlet.consensus.com [157.22.240.90])
 by mail.proper.com (8.8.8/8.8.5) with SMTP id CAA02265
 for <ietf-tls-archive@imc.org>; Tue, 2 Feb 1999 02:24:46 -0800 (PST)
Message-ID: <A9B9B14D4F3FD211857A00A0C9DDB07B164A3D@schzmxs1.europe.entrust.com>
From: Rene Eberhard <rene.eberhard@entrust.com>
To: "IETF Transport Layer Security WG" <ietf-tls@lists.consensus.com>
Cc: "'Bodo_Moeller@public.uni-hamburg.de'"
  <Bodo_Moeller@public.uni-hamburg.de>
Subject: RE: RFC 2246
Date: Tue, 2 Feb 1999 05:19:33 -0500 
MIME-Version: 1.0
Content-Type: text/plain;
 charset="iso-8859-1"
List-Unsubscribe: <mailto:leave-ietf-tls-435N@lists.consensus.com>
List-Software: Lyris Server version 3.0
List-Subscribe: <mailto:subscribe-ietf-tls@lists.consensus.com>
List-Owner: <mailto:owner-ietf-tls@lists.consensus.com>
X-List-Host: Consensus Development Corp <http://www.consensus.com/>
Reply-To: "IETF Transport Layer Security WG" <ietf-tls@lists.consensus.com>
Sender: bounce-ietf-tls-435@lists.consensus.com
X-Lyris-Message-Id: <LYR435-4822-1999.02.02-02.29.12--ietf-tls-archive#imc.org@lists.consensus.com>
Precedence: bulk
X-List-Host: SKYLIST.net <http://www.SKYLIST.net/>

Hi

>   [...]        All authentication in the protocol relies on 
> the security
>   of the algorithms negotiated at [early handshake] stage.  Now assume
>   a very strong
>   attacker whose equipment and algorithmic know-how allows him to
>   decrypt messages encrypted for weak public keys, e.g. by factoring a
>   512 bit RSA modulus during its lifetime.  (One might argue 
> that likely
>   No Such Attacker exists, but better safe than sorry.)

Am I right in understanding that you are talking about the lifetime
of a temporary RSA key? According to D.1 we assume that the attacker
can factoring the key within one day.

Although the described attack is based on factoring an export RSA key
(which is between 328 and 512 bits) it is worth picking up the 
discussion.


>   If the server offers the RSA_EXPORT key exchange method 
> with a 512 bit
>   public key, obviously there is no security against this 
> attacker: The
>   attacker deletes the strong methods from the cipher suite 
> list in the
>   ClientHello message, the server then presents its weak certificate,
>   the client sends the weakly encrypted premaster secret across the
>   network, the attacker obtains the premaster secret and uses it to
>   "authenticate" to both parties.

The attacker can fake the finished message at the end of the HS
because he owns the premaster secret.


>   Thus, the server should not use RSA_EXPORT with 512 bit public keys.
>   Fortunately, there are other exportable key exchange method that
>   include strong signatures: In the case of RSA_EXPORT with a 1024 bit
>   public key, this strong public key can be used to sign a 
> temporary 512
>   bit RSA key (Appendix D.1 gives recommendations on how often this
>   temporary key should be changed), which is then used to encrypt the
>   premaster secret.  

It is not always possible that an export server can generate strong RSA
signing key pairs. Whether an RSA key can be used for signing only (instead
for
key encipherment) is prescribed by the CA's policy.


> Unfortunately, the strong authentication provided
>   by the 1024 bit RSA key is not used properly to thwart the attack
>   described above: The signature covers, besides the 
> temporary key, only
>   the nonces ClientHello.random and ServerHello.random.  This 
> binds the
>   temporary key to the current connection, but that is not enough:
>   The signature also needs to cover ClientHello.cipher_suites (and, in
>   order to be prepared for future protocol changes, also
>   ClientHello.client_version).  Only then, there is strong
>   authentication for _why_ the server chose an export-weakened cipher.

I completely agree with you. I'd additionally add the selected cipher suite 
to the signature. This prevents the relabeling of a selected cipher suite.

And even more. There could be an additional HS message in the server's
reply.
If the server only sends its certificate which includes key agreement /
exchange
parameters the client never knows whether the server got the entire client 
hello message. (If an attacker obtained the premaster secret during HS.)
But this requires that the server always has an signature-capable
certificate.

   
>   I did not find this attack mentioned in the David Wagner and Bruce
>   Schneier's paper "Analysis of the SSL 3.0 protocol" (November
>   19, 1996).  They have a section on "Key-exchange algorithm 
> rollback",
>   but their attack is about relabeling Diffie-Hellman 
> parameters as RSA
>   parameters (the strong signature should also cover a label that
>   explicitly says which key exchange method the server picked).

I must admit that I don't understand why the signature structure hasn't
been improved. The 'relabeling Diffie-Hellman' problem still exists.
And the relabeling problem could get more importance when TLS uses
ECC ciphers!


> Later observations on the protocol drafts (quoted from a message which
> I mailed on 1998-11-22 to a different list because this one still was
> closed) include
> 
>               [...] that the draft excludes strong temporary RSA keys
>   unless the public key in the certificate "cannot be used for
>   encryption" (appendix D.1) -- i.e., strong temporary 
> parameters either
>   must be DHE parameters, or the server certificate must have keyUsage
>   restricted accordingly.  For some reason, the TLS drafts do 
> not allow
>   strong-crypto forward secrecy for RSA-only implementations 
> unless the
>   CA put a "keyUsage" extension in the server's X.509 certificate that
>   ensures that the key "cannot be used for encryption". -- Maybe the
>   draft authors were not even thinking of "keyUsage" restrictions --
>   they talk of "X509v3" certificates, but the references list the
>   prehistoric 1988 version of X.509 -- i.e., X.509 v1.
> 
> The drafts don't even mention forward secrecy, while it is a
> subject that definitely ought to be explained in the security
> considerations section.

I agree.

> Finally, the definitions of ASN.1Cert and certificate_list have
> discrepancies between section 7.4.2 and appendix A.4.2.  The former
> are correct:
> 
>        opaque ASN.1Cert<1..2^24-1>;
> 
>        struct {
>            ASN.1Cert certificate_list<0..2^24-1>;
>        } Certificate;
> 
> The latter, reproduced below, are not -- not that "opaque
> ASN.1Cert<2^24-1>" does not even match the "T T'<floor..ceiling>"
> syntax defined in section 4.3.
> 
>     opaque ASN.1Cert<2^24-1>;
> 
>     struct {
>         ASN.1Cert certificate_list<1..2^24-1>;
>     } Certificate;


Still appears in the RFC =(.

Regards Rene

---
You are currently subscribed to ietf-tls as: [ietf-tls-archive@imc.org]
To unsubscribe, forward this message to leave-ietf-tls-435N@lists.consensus.com