Subject: Re: Curve25519/448 key agreement for SSH

From: denis bider <[email-masked]>
Date: Thu, 12 Nov 2015 12:07:08 +0000

> If implementers are interested in "fixing" this while we go
> through this process, we have that opportunity. There is
> no direct backwards compatibility problem to care about,
> since we are registering a new name.  

I agree, but it does seem like it would really require re-specifying K to be a "string", and just for these particular algorithms.

With regard to compatibility - if there's a standardized name, then for use in Bitvise SSH Server and Client, I am almost certainly going to implement only the standardized name. Folks who care highly about these algorithms are probably not going to have second thoughts about using the latest versions of their software.

Folks who use older versions are typically people who don't care about CBC until it comes up in a security scan... At which point they grudgingly consider upgrading their 10 year old version. :)

----- Original Message -----
From: Simon Josefsson 
Sent: Thursday, November 12, 2015 03:17
To: denis bider 
Cc: [email-masked] ; [email-masked] 
Subject: Re: Curve25519/448 key agreement for SSH

denis bider <[email-masked]> writes:

> But X and K are different in each key exchange. The only way to make
> them same would be for both parties to conspire.

It doesn't matter if they are different -- a listening entity may be
able to use a side channel (e.g., time) to infer wether the parties
hashed X or X+1 bytes, which leaks one bit of the secret.

> I have suggested solving this by reinterpreting X as an already
> encoded K, which may be negative. Well - that has a different issue:
> it violates mpint encoding when the first byte of X is zero...
>
> All things considered, I don't think it really matters which way this
> is resolved. Just please make sure to be clear when you specify it. :)
> An imprecise specification may lead to problems that manifest in
> e.g. 1/256 of key exchanges.

Yep.  I don't care strongly about this point, but I do share your strong
opinion that it has to be clearly specified.  Right now I'm inclined to
describe exactly what libssh/OpenSSH implements and describe the
vulnerability.

If implementers are interested in "fixing" this while we go through this
process, we have that opportunity.  There is no direct backwards
compatibility problem to care about, since we are registering a new
name.  However, implementations will likely need to support both for
quite some time, and having the two implementations differ has code
maintenance costs.  It seems Aris and Damien represent two significant
implementations of this, so if they can agree on this, we have a way
forward.

/Simon

>
> Simon Josefsson <[email-masked]> , 11/12/2015 8:50 AM:
> denis bider <[email-masked]> writes: 
>  
>> Simon - 
>> 
>> 
>>> A simple approach would be to say that if the MSB is 1, 
>>> prepend a zero byte.  However, the length difference 
>>> would leak that information. 
>> 
>> The length difference might not be much of a problem, since K is never sent. 
>  
> It shouldn't be difficult to fingerprint (statistically, over many 
> connections) if a remote application performs a hash on X bytes or X+1 
> bytes.  Knowing which leaks the MSB of the derived secret. 
>  
> I'm inclined to add a security consideration describing this, and allow 
> for the potential of a nice conference paper describing how to exploit 
> this observation.  At this point, to fix this (as Damien described) 
> appear less appealing. 
>  
> /Simon

---

From: "Mark D. Baushke" <[email-masked]>
Date: Sat, 14 Nov 2015 12:00:54 -0800

denis wrote:
> Folks who use older versions are typically people who don't care about
> CBC until it comes up in a security scan... At which point they
> grudgingly consider upgrading their 10 year old version. :)

I believe that more than just ancient editions of SSH implementations
are going to need to have AES CBC mode for at least a few more years...

In the Common Criteria world, there is the
collaborative Protection Profile for Network Devices Version 1.0
https://www.niap-ccevs.org/pp/pp.cfm?id=CPP_ND_V1.0

    FCS_SSHC_EXT.1.1 The TSF shall implement the SSH protocol that
    complies with RFCs 4251, 4252, 4253, 4254, and [selection: 5647,
    5656, 6187, 6668, no other RFCs].

    ...elided...

    FCS_SSHC_EXT.1.4 The TSF shall ensure that the SSH transport
    implementation uses the following encryption algorithms and rejects
    all other encryption algorithms: aes128-cbc, aes256-cbc, [selection:
    AEAD_AES_128_GCM, AEAD_AES_256_GCM, no other algorithms].

The AEAD_AES_128_GCM and AEAD_AES_256_GCM as specified in RFC 5647 is
not implemented exactly by a number of SSH implementations, so that
tends to leave aes128-cbc and aes256-cbc for those trying to obtain
a Common Criteria CPP_ND_V1.0 certification.

While it may be possible to change this going forward, it probably means
that one or more folks from the technical community need to participate
in the Technical Communities by asking [email-masked] ...

| Call for Participants in Technical Communities (26 August 2015)
| 
| The National Information Assurance Partnership/Common Criteria
| Evaluation and Validation Scheme (NIAP/CCEVS) is inviting industry,
| government, end users, academic institutions, and labs with relevant
| technology expertise and research focus to participate in the
| following Technical Communities (TCs). If you are interested in
| joining a technical community and participating in the development
| of Protection Profiles for these technologies, please contact
| NIAP/CCEVS at:
| 
|     Secure Shell (SSH)    [email-masked]
| 
|         VPN Client    [email-masked]

	-- Mark

---

From: [email-masked] (Niels Möller)
Date: Mon, 16 Nov 2015 20:28:38 +0100

denis bider <[email-masked]> writes:

> I agree, but it does seem like it would really require re-specifying K
> to be a "string", and just for these particular algorithms.

That sounds a bit awkward, but maybe it's not a big deal to actually
implement? Do we ever do any integer operations of K? (Except internal
to the key exchange). And for the old dh key exhange algorithms, we're
converting the integer to a string, and it shouldn't be a big deal if we
think of "K" as the value before or after that conversion.

So I think we should seriously consider thinking about K as a string,
and specify curve25519 with that view.

James Cloos <[email-masked]> writes:

> Given that one of the design goals of the modern curves is to exchange
> the public data as opaque bit strings, the protocol should not use
> anything like a mpint to exchange the keys but instead should exchange
> them as the opaque bit strings they are.

I think the issue is not the messages in the curve25519 dh exchange
itself, but the representation of the *output* of the key exchange.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

---

From: [email-masked] (Niels Möller)
Date: Mon, 16 Nov 2015 21:50:13 +0100

> think of "K" as the value before or after that conversion.

I've now reread RFC 4253, section 7.2, and my corresponding source code,
to have a closer look.

: The key exchange produces two values: a shared secret K, and an
: exchange hash H.

Here, H is clearly a string, and it's construction depends on the key
exchange method. That K is an integer is stated in a parenthesis,

:    o  Initial IV client to server: HASH(K || H || "A" || session_id)
:       (Here K is encoded as mpint and "A" as byte and session_id as raw
:       data.  "A" means the single character A, ASCII 65).

So K's contribution to the hash input is a length field, followed by
network-byte order bytes, following ssh rules on how to deal with sign
bit, etc. (The specification really isn't crystal clear, e.g., I think H
too is "raw data", not preceded by a length field like a string).

I don't see any serious practical problem if we for curve25519 specify
that we do HASH(K || H || ...) where K is encoded as a string, i.e.,
four octets length, 0,0,0,32, followed by the curve25519 fixed-size
output string (which happens to be an x-coordinate in little-endian
order, iirc).

My implementation actually represents K as a string already, with the
conversion from integer to string done in the dh code, not in the
generic key exchange code, which I think at least shows that there
should be no great difficulty in treating K as a string.

I think I'd prefer that we do the right thing here, even if that means
we specify something not quite compatible with
[email-masked]. Other opinions?

Regards,
/Niels