Subject: [Cfrg] AES-GCM-SIV: Expository interpretation of POLYVAL as an IUF construction

From: Björn Edström <[email-masked]>
Date: Tue, 1 Jan 2019 12:33:46 +0100

This is maybe obvious, stupid, or both, but I felt like sharing:

In the internet draft for AES-GCM-SIV, POLYVAL is explained as a function
POLYVAL(H, X_1. X_2...) and the AES-GCM-SIV construction is shown as a
special implementation of AES-CTR using this POLYVAL function in the
encrypt() and decrypt() step. This is tight, performant, and clear.

As an alternative way to explain the AES-GCM-SIV construction, consider
instead trying to implement it as much as possible as composition of
primitives. That is:

* Given a decently standard AES-CTR implementation
* ...And interpreting POLYVAL as an Init/Update/Finalize hash construction
- a primitive in it's own right

Then the entirety of AES-GCM-SIV can be implemented as a few lines of glue
code. Have a look:
https://github.com/bjornedstrom/aes-gcm-siv-py/blob/master/reference.py

Semi-philosophical point: This approach is only reasonable if you "lift"
POLYVAL into a valuable and generic primitive on it's own, that is not just
a detail of AES-GCM-SIV but something that is useful in it's own. For
cognitive load reasons, then POLYVAL can be treated as a black box similar
to hash functions in general, instead of something that is "part of"
AES-GCM-SIV. </weird crackpot comment>

Cheers
Bjorn

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 23 Jan 2019 20:15:55 -0800

> AES-GCM-SIV. </weird crackpot comment>

I've written a toy Rust implementation of POLYVAL along these lines with an
IUF API (which is untested and almost certainly broken):

https://github.com/miscreant/miscreant.rs/blob/047ae8b3fd68d62eeb1e8510110439ba24473df3/src/polyval.rs

I attempted to implement an idea which is described (although I'm unsure if
it's actually "recommended") in the RFC: using POLYVAL to implement GHASH.

If we could get this to work, I think a neat thing to attempt would be
implementing both AES-GCM and AES-GCM-SIV using a shared "polyval" library
(a.k.a. crate in Rust terminology).

We've also discussed creating a Rust trait (more or less an interface) for
universal hash functions, which could have a common IUF API that an
instantiation of POLYVAL (or GHASH in terms of polyval) could implement.

-- 
Tony Arcieri