Incrementality and deck functions - Simple protocols and efficient 2020-01-31آ  Incrementality and deck

  • View
    0

  • Download
    0

Embed Size (px)

Text of Incrementality and deck functions - Simple protocols and efficient 2020-01-31آ  Incrementality and...

  • Incrementality and deck functions Simple protocols and efficient constructions

    in symmetric cryptography

    Gilles Van Assche1

    1STMicroelectronics

    FOSDEM 2020 Brussels, Belgium, February 1, 2020

    1 / 30

  • Joint work with the Keccak team

    Guido Bertoni Italy Joan Daemen The Netherlands Seth Hoffert USA Michaël Peeters Belgium Gilles Van Assche Belgium Ronny Van Keer Belgium

    https://keccak.team/ 2 / 30

    https://keccak.team/

  • What we do: permutation-based crypto

    Hashing Keccak, SHA-3, SHAKE, cSHAKE, ParallelHash, … KangarooTwelve [ultra-fast, most third-party cryptanalysis to date]

    Symmetric-key encryption and/or authentication Keyed duplex: Ketje, Keyak, Xoodyak Farfalle: Kravatte, Xoofff [fast from small to big platforms]

    Re-thinking symmetric crypto Deck function interface Simpler authenticated encryption schemes

    3 / 30

  • What we do: permutation-based crypto

    Hashing Keccak, SHA-3, SHAKE, cSHAKE, ParallelHash, … KangarooTwelve [ultra-fast, most third-party cryptanalysis to date]

    Symmetric-key encryption and/or authentication Keyed duplex: Ketje, Keyak, Xoodyak Farfalle: Kravatte, Xoofff [fast from small to big platforms]

    Re-thinking symmetric crypto Deck function interface Simpler authenticated encryption schemes

    3 / 30

  • What we do: permutation-based crypto

    Hashing Keccak, SHA-3, SHAKE, cSHAKE, ParallelHash, … KangarooTwelve [ultra-fast, most third-party cryptanalysis to date]

    Symmetric-key encryption and/or authentication Keyed duplex: Ketje, Keyak, Xoodyak Farfalle: Kravatte, Xoofff [fast from small to big platforms]

    Re-thinking symmetric crypto Deck function interface Simpler authenticated encryption schemes

    3 / 30

  • Outline

    1 Why is incrementality useful? (Example: Disco)

    2 What are deck functions?

    3 How to use a deck function?

    4 How to build a fast deck function?

    4 / 30

  • Why is incrementality useful? (Example: Disco)

    Outline

    1 Why is incrementality useful? (Example: Disco)

    2 What are deck functions?

    3 How to use a deck function?

    4 How to build a fast deck function?

    5 / 30

  • Why is incrementality useful? (Example: Disco)

    Duplex object Duplex object = sponge function with incrementality

    0

    0

    r

    c

    outer inner

    initialize

    pad

    f

    duplexing

    σ0 Z0

    pad

    f

    duplexing

    σ1 Z1

    pad

    f

    duplexing

    σ2 Z2

    [Selected Areas in Cryptography 2011]

    6 / 30

  • Why is incrementality useful? (Example: Disco)

    Strobe

    Layer above a duplex object compliant with cSHAKE [NIST SP 800-185]

    Safe and easy syntax, to achieve, e.g., secure channels hashing of protocol transcripts signatures over a complete session

    Very compact implementation

    [Mike Hamburg, Real World Crypto 2017]

    7 / 30

  • Why is incrementality useful? (Example: Disco)

    Strobe functions

    figures courtesy of David Wong

    8 / 30

  • Why is incrementality useful? (Example: Disco)

    Example: protocol

    KEY(shared key K) AD[nonce](seq. number i) AD[auth-data](IP1||IP2) send_ENC(“GET file”) send_MAC(128 bits) recv_ENC(ciphertext buffer) recv_MAC(128 bits)

    9 / 30

  • Why is incrementality useful? (Example: Disco)

    Example: protocol

    KEY(shared key K) set key K, empty context X AD[nonce](seq. number i) AD[auth-data](IP1||IP2) send_ENC(“GET file”) send_MAC(128 bits) recv_ENC(ciphertext buffer) recv_MAC(128 bits)

    9 / 30

  • Why is incrementality useful? (Example: Disco)

    Example: protocol

    KEY(shared key K) set key K, empty context X AD[nonce](seq. number i) X← (i) ◦ “nonce” ◦ X AD[auth-data](IP1||IP2) send_ENC(“GET file”) send_MAC(128 bits) recv_ENC(ciphertext buffer) recv_MAC(128 bits)

    9 / 30

  • Why is incrementality useful? (Example: Disco)

    Example: protocol

    KEY(shared key K) set key K, empty context X AD[nonce](seq. number i) X← (i) ◦ “nonce” ◦ X AD[auth-data](IP1||IP2) X← (IP1||IP2) ◦ “auth-data” ◦ X send_ENC(“GET file”) send_MAC(128 bits) recv_ENC(ciphertext buffer) recv_MAC(128 bits)

    9 / 30

  • Why is incrementality useful? (Example: Disco)

    Example: protocol

    KEY(shared key K) set key K, empty context X AD[nonce](seq. number i) X← (i) ◦ “nonce” ◦ X AD[auth-data](IP1||IP2) X← (IP1||IP2) ◦ “auth-data” ◦ X send_ENC(“GET file”) ciphertext = encK,X(“GET file”)

    X← “GET file” ◦ X send_MAC(128 bits) recv_ENC(ciphertext buffer) recv_MAC(128 bits)

    9 / 30

  • Why is incrementality useful? (Example: Disco)

    Example: protocol

    KEY(shared key K) set key K, empty context X AD[nonce](seq. number i) X← (i) ◦ “nonce” ◦ X AD[auth-data](IP1||IP2) X← (IP1||IP2) ◦ “auth-data” ◦ X send_ENC(“GET file”) ciphertext = encK,X(“GET file”)

    X← “GET file” ◦ X send_MAC(128 bits) MACK(X) recv_ENC(ciphertext buffer) recv_MAC(128 bits)

    9 / 30

  • Why is incrementality useful? (Example: Disco)

    Example: protocol

    KEY(shared key K) set key K, empty context X AD[nonce](seq. number i) X← (i) ◦ “nonce” ◦ X AD[auth-data](IP1||IP2) X← (IP1||IP2) ◦ “auth-data” ◦ X send_ENC(“GET file”) ciphertext = encK,X(“GET file”)

    X← “GET file” ◦ X send_MAC(128 bits) MACK(X) recv_ENC(ciphertext buffer) plaintext = decK,X(ciphertext)

    X← plaintext ◦ X recv_MAC(128 bits)

    9 / 30

  • Why is incrementality useful? (Example: Disco)

    Example: protocol

    KEY(shared key K) set key K, empty context X AD[nonce](seq. number i) X← (i) ◦ “nonce” ◦ X AD[auth-data](IP1||IP2) X← (IP1||IP2) ◦ “auth-data” ◦ X send_ENC(“GET file”) ciphertext = encK,X(“GET file”)

    X← “GET file” ◦ X send_MAC(128 bits) MACK(X) recv_ENC(ciphertext buffer) plaintext = decK,X(ciphertext)

    X← plaintext ◦ X recv_MAC(128 bits) check that MAC = MACK(X)

    9 / 30

  • Why is incrementality useful? (Example: Disco)

    The Noise protocol framework

    Framework for crypto protocols based on Diffie-Hellman public-key handshake mechanism secret-key encryption and authentication used in WhatsApp, WireGuard, …

    [Trevor Perrin, Real World Crypto 2018]

    10 / 30

  • Why is incrementality useful? (Example: Disco)

    Inside Noise

    figure courtesy of David Wong

    11 / 30

  • Why is incrementality useful? (Example: Disco)

    Disco

    Disco = Noise + Strobe [David Wong, Black Hat Europe 2017]

    12 / 30

  • Why is incrementality useful? (Example: Disco)

    Inside Disco

    figure courtesy of David Wong

    13 / 30

  • Why is incrementality useful? (Example: Disco)

    Duplex object inside Disco

    figure courtesy of David Wong

    14 / 30

  • Why is incrementality useful? (Example: Disco)

    Implementation complexity

    figure courtesy of David Wong

    15 / 30

  • What are deck functions?

    Outline

    1 Why is incrementality useful? (Example: Disco)

    2 What are deck functions?

    3 How to use a deck function?

    4 How to build a fast deck function?

    16 / 30

  • What are deck functions?

    Definition of a deck function

    A deck function FK

    Z = 0n + FK ( X(m) ◦ · · · ◦ X(1)

    ) ≪ q

    doubly extendable cryptographic keyed function

    17 / 30

  • What are deck functions?

    Definition of a deck function

    A deck function FK

    Z = 0n + FK ( X(m) ◦ · · · ◦ X(1)

    ) ≪ q

    Input: sequence of strings X(m) ◦ · · · ◦ X(1)

    17 / 30

  • What are deck functions?

    Definition of a deck function

    A deck function FK

    Z = 0n + FK ( X(m) ◦ · · · ◦ X(1)

    ) ≪ q

    Input: sequence of strings X(m) ◦ · · · ◦ X(1) Output: potentially infinite output

    pseudo-random function of the input taking n bits starting from offset q

    17 / 30

  • What are deck functions?

    Definition of a deck function

    A deck function FK

    Z = 0n + FK ( X(m) ◦ · · · ◦ X(1)

    ) ≪ q

    Efficient incrementality

    Extendable input 1 Compute FK (X) 2 Compute FK (Y ◦ X): cost independent of X

    17 / 30

  • What are deck functions?

    Definition of a deck function

    A deck function FK

    Z = 0n + FK ( X(m) ◦ · · · ◦ X(1)

    ) ≪ q

    Efficient incrementality

    Extendable input 1 Compute FK (X) 2 Compute FK (Y ◦ X): cost independent of X

    Extendable output 1 Request n1 bits from offset 0 2 Request n2 bits from offset n1: cost independent of n1

    17 / 30

  • How to use a deck function?

    Outline

    1 Why is incrementality useful? (Example: Disco)

    2 What are deck functions?

    3 How to use a deck function?

    4 How to build a fast deck function?

    18 / 30