lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  PHC 
Open Source and information security mailing list archives
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [day] [month] [year] [list]
Date: Sun, 23 Mar 2014 01:04:54 -0400
From: Daniel Franke <>
Subject: Shortcut-free functions

The following definition grew out of an attempt at formally
characterizing the manner in which EARWORM relies on the AES round
function. I think some other submitters might find the concept useful in
their own security analyses.

Hopefully all the Unicode in this email renders properly for most of

Let {fₙ | n ∈ ℕ} be a family of functions with signature

    fₙ : {0,1}ⁿ × {0,1}ⁿ → {0,1}ⁿ

such that fₙ is computable in polynomial time wrt n. Let

    gₙ : ℕ × ({0,1}ⁿ)[L] × {0,1}ⁿ → {0,1}ⁿ

(this notation for the second argument denotes a zero-indexed array of L
n-bit strings), where

    gₙ(0, K, m) = m
    gₙ(i, K, m) = f(K[i-1], g(i-1, K, m)).

gₙ is undefined when i ≥ L. Essentially, gₙ iterates fₙ by folding it
over K, using m as a starting value.

Consider the following game. The defender fixes the parameters n and L,
chooses K ← ({0,1}ⁿ)[L] and m ← {0,1}ⁿ uniformly at random, and outputs
n, L, and K, keeping m secret. The adversary then outputs a circuit
    h : {0,1}ⁿ → {0,1}ⁿ.

The attacker wins iff

   h(m) = gₙ(L, K, m).

{fₙ} is defined to be a "shortcut-free" family of functions iff for all
adversaries A such that

   * A executes in probabalistic polynomial time wrt n and L, and
   * the circuit-size complexity of A's output is o(L) (sic: little-o

A's success probability is less than ε(n), where ε is a negligible

A particular function fₙ may informally be said to be shortcut-free if
ε(n) is "sufficiently" small.

This definition basically says that the attacker can't do any
precomputation to usefully "compress" K for the purpose of computing gₙ.
The first restriction on the set of adversaries says that the
precomputation is tractable, and the second restriction says that it
produces a beneficial result.

For a simple example of a function family that is *not* shortcut-free,
consider addition, where fₙ adds two n-bit integers modulo 2ⁿ. So, gₙ
computes m + ∑K. In this case the adversary can precompute ∑K and then
output a circuit that simply performs the single remaining addition (the
complexity of which does not depend on L), thus winning the game with

EARWORM, in order to satisfy its security goals, relies upon the
conjecture that the AES round function is shortcut-free.

Powered by blists - more mailing lists