Paper 2019/016

Fast Message Franking: From Invisible Salamanders to Encryptment

Yevgeniy Dodis, Paul Grubbs, Thomas Ristenpart, and Joanne Woodage

Abstract

Message franking enables cryptographically verifiable reporting of abusive content in end-to-end encrypted messaging. Grubbs, Lu, and Ristenpart recently formalized the needed underlying primitive, what they call compactly committing authenticated encryption (AE), and analyzed the security of a number of approaches. But all known secure schemes are still slow compared to the fastest standard AE schemes. For this reason Facebook Messenger uses AES-GCM for franking of attachments such as images or videos. We show how to break Facebook’s attachment franking scheme: a malicious user can send an objectionable image to a recipient but that recipient cannot report it as abuse. The core problem stems from use of fast but non-committing AE, and so we build the fastest compactly committing AE schemes to date. To do so we introduce a new primitive, called encryptment, which captures the essential properties needed. We prove that, unfortunately, schemes with performance profile similar to AES-GCM won’t work. Instead, we show how to efficiently transform Merkle-Damgärd-style hash functions into secure encryptments, and how to efficiently build compactly committing AE from encryptment. Ultimately our main construction allows franking using just a single computation of SHA-256 or SHA-3. Encryptment proves useful for a variety of other applications, such as remotely keyed AE and concealments, and our results imply the first single-pass schemes in these settings as well.

Note: Full version. Fixed broken cites

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in Crypto 2018
Keywords
authenticated encryptionencrypted messaging
Contact author(s)
joanne woodage 2014 @ live rhul ac uk
pag225 @ cornell edu
History
2019-01-15: last of 2 revisions
2019-01-09: received
See all versions
Short URL
https://ia.cr/2019/016
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/016,
      author = {Yevgeniy Dodis and Paul Grubbs and Thomas Ristenpart and Joanne Woodage},
      title = {Fast Message Franking: From Invisible Salamanders to Encryptment},
      howpublished = {Cryptology ePrint Archive, Paper 2019/016},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/016}},
      url = {https://eprint.iacr.org/2019/016}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.