AES-SIV

[tarcieri]

I'm looking for a key-wrapping algorithm for credentials which use a "holder-of-key"/"proof-of-possession" system for split credentials mediated by multiple parties (similar features are available in both the Macaroons and JWT credential systems). The goal of using a key-wrapping algorithm is to secure a randomly generated symmetric key, and allow for omitting the nonce (so as to make the credential shorter) with the contract that all we're encrypting are 128-bit randomly generated keys, and we promise to always generate a random key for every request so keys never repeat.

AES-GCM-SIV (https://github.com/briansmith/ring/issues/412) is likely to be the widely supported version of such a scheme. But the spec has been in flux for quite some time, and it might take longer still until a good implementation makes it into BoringSSL.

It'd be nice to have something in the meantime, provided it's robust. I think AES-SIV is a nice candidate:

http://web.cs.ucdavis.edu/~rogaway/papers/siv.pdf

AES-SIV also has the advantages that it only relies on the AES function (in the form of AES-CTR and CMAC) along with a dbl() function which, if I have it right, looks something like this:

fn dbl(s: u128) -> u128 {
    if s & 0x80000000000000000000000000000000 != 0 {
        (s << 1) ^ 0b10000111
    } else {
        s << 1
    }
}

(Warning: Untested unverified non-constant-time nightly-only 128-bit key size only do not use this code)

An optimized constant-timeish version that uses SHLDQ looks more like this (thanks @eternaleye):

#![feature(i128_type)]

pub fn dbl(s: u128) -> u128 {
    (s << 1) ^ (
        // Extend the high bit of s to the full length
        (((s as i128) >> 127) as u128)
        // then AND with the appropriate constant
        & 0b10000111
        // So that if the high bit is unset, we XOR with zero,
        // and if it is set, we XOR with the constant
    )
}

AES-SIV seems attractive over AES-GCM-SIV anywhere you don't have GCM acceleration (or it's expensive), a case I so happen to be in (ask me offline for details if you're interested). Though my case isn't, "IoT" would probably be a case where this sort of construction is helpful, especially on devices that have the AES function hardware accelerated, but do not have instructions to accelerate GHASH.

The scheme takes an arbitrary number of header fields which are fed into CMAC. The paper suggests two modes, a keywrap mode where headers are omitted (so a fully deterministic keywrap mode), and an MRAE mode where a user supplies a random nonce. It seems this could map to ring's AEAD API, using two headers with the first as a nonce and the second header as optional authenticated data.

I was looking at https://github.com/briansmith/ring/pull/369 and I'm unclear whether it would be a prerequisite for integrating with the AEAD API. To actually support a keywrap mode though, I'd think you'd need to add a new keywrap API that explicitly doesn't take a nonce. I understand there might be some footgun potential here if people accidentally abuse it for deterministic encryption and repeat messages.

Other than that, this seem seems fairly easy to implement in pure Rust using only the AES function and the above dbl() function.

Would there be interest in supporting it (i.e. if it were contributed and of sufficiently good quality)?

[briansmith]

Tony Arcieri notifications@github.com wrote:

It'd be nice to have something in the meantime, provided it's robust. I think AES-SIV is a nice candidate:

In general, I'd prefer AES-SIV over AES-KW. I also think AES-SIV is likely to be more interoperable with other things

Some questions:

Is AES-SIV a FIPS-approved key wrapping algorithm? If so, link?

Is AES-SIV in JOSE? If so, link?

Is AES-SIV in WebCrypto? If so, link?

Which crypto libraries/APIs, especially within BoringSSL, OpenSSL, Windows CAPI, Windows CNG, PKCS#11, Java SE, Android, support AES-SIV?

AES-SIV also has the advantages that it only relies on the AES function (in the form of AES-CTR and CMAC) along with a dbl() function which, if I have it right, looks something like this:

![feature(i128_type)]

pub fn dbl(s: u128) -> u128 { (s << 1) ^ ((((s as i128) >> 127) as u128) & 0b10000111) }

Yes, the AES-SIV construction is a lot better than AES-KW in this respect. Note that in ring we'd implement this function in C in the near term, until we find a solution to side-channel-resistance stuff within Rust. (I'm not saying C is better w.r.t. side channel resistance, but we split things this way in ring in the short term for reasons I'm hoping to write about in detail at some point.)

Also note in particular that some AES operations in ring may be assuming particular alignment, especially particular alignment of the key, and as of right now we don't expose AES_KEY to Rust.

So it's probably much more straightforward to do the lowest-level parts in C for now, while doing the higher-level parts in Rust. But I could be wrong.

The scheme takes a random, user-supplied nonce along with an arbitrary number of additional header fields which are fed into CMAC. It seems this could map to an AEAD API, using the second header as optional authenticated data.

If the use case is key wrapping then my first instinct is that we should just make a new API for key wrapping, rather than extending the AEAD API. We could have a ring::key_wrap module, for example, which has a ring::key_wrap::Key type, which enables unwrap_aead_{opening, sealing}_key() -> ring::aead::{OpeningKey, SealingKey} and analogous wrap_aead_key() operations.

I was looking at #369 https://github.com/briansmith/ring/pull/369 and I'm unclear whether it would be a prerequisite for this sort of thing.

Not sure. My instinct is that if we were to expose it through the AEAD API, then probably. Otherwise, probably not.

In general, I think it's good and necessary to have a key wrapping API in ring and I'm not sure there's a better one than AES-SIV that has any kind of standard describing it.

[briansmith]

I also think AES-SIV is likely to be more interoperable with other things

... than AES-GCM-SIV, and most other things, except, unfortunately, AES-KW.

[eternaleye]

Note that in ring we'd implement this function in C in the near term, until we find a solution to side-channel-resistance stuff within Rust. (I'm not saying C is better w.r.t. side channel resistance, but we split things this way in ring in the short term for reasons I'm hoping to write about in detail at some point.)

In that case, it might be worth pushing it all the way down into asm - it's a pretty darn short sequence. Copying from godbolt:

example::dbl:
        pushq   %rbp
        movq    %rsp, %rbp
        movq    %rsi, %rdx
        shldq   $1, %rdi, %rdx
        addq    %rdi, %rdi
        sarq    $63, %rsi
        andl    $135, %esi
        xorq    %rdi, %rsi
        movq    %rsi, %rax
        popq    %rbp
        retq

If the use case is key wrapping then my first instinct is that we should just make a new API for key wrapping, rather than extending the AEAD API. We could have a ring::key_wrap module, for example, which has a ring::key_wrap::Key type, which enables unwrap_aead_{opening, sealing}_key() -> ring::aead::{OpeningKey, SealingKey} and analogous wrap_aead_key() operations.

A separate key wrap API seems entirely sensible, though I will note that AES-SIV is also a very serviceable AEAD mode (MRAE, in fact). I personally would like to use it in order to implement Rogaway's CHAIN mode for another project.

[tarcieri]

Is AES-SIV a FIPS-approved key wrapping algorithm?

I believe only AES-KW is. I can double check.

Is AES-SIV in JOSE?

Well, here's the relevant RFCs:

https://tools.ietf.org/html/rfc7517 https://tools.ietf.org/html/rfc7518

which lists AES-KW and a GCM mode I assume is AES-GCM-SIV. So that'd be a no.

Is AES-SIV in WebCrypto?

No

[briansmith]

eternaleye notifications@github.com wrote:

Note that in ring we'd implement this function in C in the near term, until we find a solution to side-channel-resistance stuff within Rust. (I'm not saying C is better w.r.t. side channel resistance, but we split things this way in ring in the short term for reasons I'm hoping to write about in detail at some point.)

In that case, it might be worth pushing it all the way down into asm - it's a pretty darn short sequence. Copying from godbolt:

example::dbl: pushq %rbp movq %rsp, %rbp movq %rsi, %rdx shldq $1, %rdi, %rdx addq %rdi, %rdi sarq $63, %rsi andl $135, %esi xorq %rdi, %rsi movq %rsi, %rax popq %rbp retq

Yes, that would be good. It may be annoying when you think about what is required to make it work for both Yasm (for Windows) and gas/clang-ml and on ARMv6+, Aaarch64, and x86, in addition to the x86-64.

If the use case is key wrapping then my first instinct is that we should just make a new API for key wrapping, rather than extending the AEAD API. We could have a ring::key_wrap module, for example, which has a ring::key_wrap::Key type, which enables unwrapaead{opening, sealing}_key() -> ring::aead::{OpeningKey, SealingKey} and analogous wrap_aead_key() operations.

A separate key wrap API seems entirely sensible, though I will note that AES-SIV is also a very serviceable AEAD mode (MRAE, in fact). I personally would like to use it in order to implement Rogaway's CHAIN mode for another project.

Perhaps. I'm just saying that if the intended purpose is key wrap then it makes sense to have a key wrap API, because in general we try to model keys using types based on their intended purpose in ring. This is why we even have separate OpeningKey and SealingKey types, for example.

[eternaleye]

Perhaps. I'm just saying that if the intended purpose is key wrap then it makes sense to have a key wrap API, because in general we try to model keys using types based on their intended purpose in ring. This is why we even have separate OpeningKey and SealingKey types, for example.

Yup; I suspect the best move might be to expose AES-SIV as a key-wrapping algorithm and an AEAD algorithm in a fully-separated, never-the-twain-shall-meet way. I was just chiming in with the utility of exposing it as an AEAD at all.

[eternaleye]

Thinking on this further, would a viable strategy for those architectures be to do as I did for the x86_64 one, and just compile the Rust function to each of them, check that the asm is const-time, and if needed fix it up for different assembler syntaxes?

[briansmith]

Thinking on this further, would a viable strategy for those architectures be to do as I did for the x86_64 one, and just compile the Rust function to each of them, check that the asm is const-time, and if needed fix it up for different assembler syntaxes?

At this time I'd rather have all the constant-time primitives expressed in C. I will convert them to Rust in another, later, phase of the project.

[briansmith]

One obstacle I noticed regarding key wrapping: I guess that we will eventually support PKCS#8 keys authenticated and encrypted inside some (minimal subset of) CMS structure. CMS identifies algorithms by OID (ASN.1 Object Identifier), but no OID has ever been registered for AES-SIV, AFAICT.

[eternaleye]

Ah; that's not what I meant. My response was meant to be addressing this line, regarding pure assembly implementation for dbl:

It may be annoying when you think about what is required to make it work for both Yasm (for Windows) and gas/clang-ml and on ARMv6+, Aaarch64, and x86, in addition to the x86-64.

I was proposing that I could take the already-written Rust (which generates sane asm on x86-64), use it to generate asm for all of the above, hand-validate the asm, and then commit only the asm.

[briansmith]

Yes, I understand that, but what I mean is that I want the source of the generated asm to be C for the time being. Then we can publish the steps necessary to generate the asm from the C and then do as you say and check in the asm (and C).

[eternaleye]

Ah, fair enough.

[eternaleye]

One other thing worth bringing up:

... than AES-GCM-SIV, and most other things, except, unfortunately, AES-KW.

From a mail Adam Langley sent to the CFRG on Jan 19:

On Wed, Jan 18, 2017 at 7:53 PM, Brian Smith brian@briansmith.org wrote:

Perhaps: "We recommend instead that an implementation try to avoid repeating a nonce for a specific key, just like it would it would do for an AEAD that isn't nonce-misuse-resistant." This shifts the emphasis away from the 2^8 number to where it belongs, IMO. Note that "256" and how it is derived and why it is safe is explained in the next paragraph anyway.

After some discussions on Twitter I've discovered that several people (possibly including Brian) understand "nonce-misuse resistant" to mean a stronger property than AES-GCM-SIV has. Namely they understood it to mean that the value of the nonce is /irrelevant/ for security, except that a fixed nonce discloses equality of plaintexts.

AES-GCM-SIV doesn't have this property. It is robust to random nonce duplication but not designed for a fixed nonce. Specifically, after 2^n full-sized (i.e. 64MB) messages, there's ~2^(96-2n) chance that two of the messages reused counter values and thus keystream. (The bounds are better if messages are smaller.)

Considering this, is AES-GCM-SIV even safe for key-wrapping at all, a use case that may need to omit the nonce entirely?

[tarcieri]

So yes, to reiterate @eternaleye here...

AES-SIV is a beautifully simple construction with provable, well-understood security properties which surpass pretty much every widely-used construction available today.

AES-GCM-SIV is inventing a performance-oriented GHASH replacement called POLYVAL which I am sure will be very fast but is ever so complicated.

I think these are both useful options, but I would love to see the simple, well-understood thing with provable security properties made available in addition to the complex, fast, not entirely well-understood thing.

[jhpratt]

@briansmith @tarcieri How likely is it that the aes_siv/aes_gcm_siv crates get merged into ring? It seems to serve the same purpose.

[tarcieri]

If there's code from those crates that would be helpful to vendor into ring I'm happy to relicense it.

However, most of the interesting parts have equivalents in BoringSSL (e.g. POLYVAL) which are more robust/better tested which would probably be more in line with how ring typically works.