Re: Read-out on offline connection ID discussion

[Mikkel Fahnøe Jørgensen <[e-mail]>]

On 25 January 2018 at 00.16.55, Eric Rescorla ([e-mail]) wrote:

I don’t understand this requirement for the CID to be 16 bytes in order to
be encrypted.
If you have a unique key you can encrypt 0, truncate and xor with the CID.
If you don’t have a unique key, you can encrypt a unique counter value and
do the same, or derive a unique key.


I don't believe what you are describing works correctly, but I'm not sure I
understand your proposal. Can you please flesh out precisely what you have
in mind? In particular, who is "you", who has the key, etc.?

I’m merely stating that if you want to encrypt with AES and you do not care
about authentication, then AES works fine with shorter inputs than 16
bytes. You may still have to provide an initialisation vector so the +n
still holds. The last block of AES-GCM is not a full block and works as i
described - see sect. 2.3 and figure 1 in link to GCM paper. If the last
block is the only block, you encrypt less than 16 bytes without any magic.

There are many reasons you might want to use 16 bytes, or you might want to
add authentication, but it is not AES itself that imposes those constraints
as already argued. My point is that if you need 16 bytes, please state why,
instead of blaming it on AES.

As to a possible scheme:

Assume a server cluster wants to encode routing data by selecting one out
of 256 possible routes and a 8 bit unique id for each route. This can be
done with 16 bits. (Not saying this is a good idea). Or, let’s make it
simple for a start: just have 1 routing bit R to choose between two servers
and 1 IV bit to identify the connection, and one phase bit P. The objective
is to make it unpredictable which server is hit. The encryption of the two
bits happen by encrypting the IV bit with a cluster key that all routers
are aware of. The phase bit is not needed but avoids guessing which router
key is active since it rotates every hour derived from a master key. The
encrypted CID is just 1 bit flipped randomly based on XOR’ing with
encrypting 1 or 0, depending the IV is 1 or 0. key = derive(master, R), P =
not P if key changed since last derivation. The encrypted CID ECID =
<AES(key, IV) XOR R, IV, P>.

We can readily extend the above to as many R bits as needed. The IV must be
unique but if we only care about making it hard to force a route rather
than protecting information, it is less critical, assuming we hide the
master key behind strong derivation.

The problem is that an attacker can easily flip the first bit in the ECID.
We can make this harder by having more than R bits than valid routes and
having more IV bits chosen at random. The R bits now either map to a valid
route or not. It becomes harder to guess a valid route.

We can make this harder by adding an auth tag - say of length 16 bits.
AES-GCM is not suited for short tags, but there CMACs that can do this I
believe (two times AES + padding and truncation to desired length, from
memory). However, if it is sufficiently hard to guess a route, and it is
easy to decide if a route is valid or not, it may not be necessary with an
auth tag.

In addition we want to identify the connection uniquely with respect to the
chosen server route so we add U bits to make the connection id unique.
These do not have to be encrypted, but they might as well be thrown in.

http://www.mindspring.com/~dmcgrew/gcm-nist-6.pdf

AES-GCM goes horribly wrong if the same encrypted counter value is used
twice - but we may not have a problem with horribly wrong in our use case,
which also only uses the CTR mode part.