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

Björn Edström <be@bjrn.se> Tue, 01 January 2019 11:34 UTC

Return-Path: <bjorn.edstrom@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id CF93912DF71 for <cfrg@ietfa.amsl.com>; Tue, 1 Jan 2019 03:34:00 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.918
X-Spam-Level:
X-Spam-Status: No, score=-0.918 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.001, FREEMAIL_FROM=0.001, FROM_EXCESS_BASE64=0.979, HEADER_FROM_DIFFERENT_DOMAINS=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=bjrn-se.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id u-eE3g0UI4Lb for <cfrg@ietfa.amsl.com>; Tue, 1 Jan 2019 03:33:58 -0800 (PST)
Received: from mail-oi1-x233.google.com (mail-oi1-x233.google.com [IPv6:2607:f8b0:4864:20::233]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B74C0127AC2 for <cfrg@irtf.org>; Tue, 1 Jan 2019 03:33:58 -0800 (PST)
Received: by mail-oi1-x233.google.com with SMTP id a77so23269498oii.5 for <cfrg@irtf.org>; Tue, 01 Jan 2019 03:33:58 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bjrn-se.20150623.gappssmtp.com; s=20150623; h=mime-version:from:date:message-id:subject:to; bh=h7pm9TPqFe0pLODeW1kV3X3fYvPKE00HCzmXl6SRSHo=; b=cIaBxCyYjvUvM9PJAFON13tPtc7z5Y+74DeJh9GMN3heV4wvfswWe+YsExgB2tMooQ Z4l7pbRXH8eorefiekSfNxtVp6G8Gqgpftair1UNzKOXoOsJsMrmLldfk3n2SuSrgwWz TOLInpLCepHaNXqqfcS2bAfe99wNXs42P0ew1qh6TNiSNltaBBgW9C2DqyHhN3PIJ+Xo IMBCXzhLbjMhDKuGeKSPHBFv31d0A+IUPXTALzY+Sb0evfqmRHGRTv41Yr8ndIGAGEJm zJ/nGDkjeIgn1oFG0q/pW4UjQ71GhrUSyBxw64vOTFOYXomjQuz3v32EebmBEf6wpQ74 Z5hg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=h7pm9TPqFe0pLODeW1kV3X3fYvPKE00HCzmXl6SRSHo=; b=N8FLPr43JK+aaVv9mHjLoBew56od39niqb8KtSGrbwtQD7DRWuVuKOgICgQ9Iukguc Ho+Hhh+A/OZF+z6LJcGZOI3iSs/5ylAqwnyfmbiYwE/te5Qw/0QrmqIllT/mSn4xN6WX hx7t4/7hvAwn7aJ0PjoH2OrWGAl26qE8uW6HhNsntJKATID6eGa9pZp3gRR3mtLD1fZJ QZHb0wevtivOo0g5sNhP/GHEl2Q6bya3DMsQm0UCSEtOeLh0+vU7cpLuHkxnUZPbIxY9 hMilwf+aJA7WgL4j8CF/xrdFx5G3wxt+VFk9iqPx1IFpEpxwmv0O06u7ggBxSx+oCeSP Otxg==
X-Gm-Message-State: AA+aEWbFF1GBTc9lileIGYYPOaEbWNJLZlQTu7MEWQI+Re2rBT6CT8+p dx3WKmnSdxFYdm1s793uy6Ug9SaYlxqHlP8BOHJjcgFv
X-Google-Smtp-Source: AFSGD/UPr1tYEhoyr8i+59s4UUjYHjzNXVql3Ml5cQ9IKal4QzmDHiuR6IX3uOzztP/BcCOK3V+X+DBdEK2Nhev5WXU=
X-Received: by 2002:a54:4f86:: with SMTP id g6mr26287395oiy.205.1546342437706; Tue, 01 Jan 2019 03:33:57 -0800 (PST)
MIME-Version: 1.0
From: =?UTF-8?B?QmrDtnJuIEVkc3Ryw7Zt?= <be@bjrn.se>
Date: Tue, 1 Jan 2019 12:33:46 +0100
Message-ID: <CAA4PzX2-k3O2EsZzhDyksDZfLYEfKjGOfrqwvdqh3e9_1WyEFw@mail.gmail.com>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="000000000000b362a3057e63e7d8"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/KMArSENuHGZimRpN_y5nGZtS7Xw>
Subject: [Cfrg] AES-GCM-SIV: Expository interpretation of POLYVAL as an IUF construction
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 01 Jan 2019 11:34:01 -0000

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