Explicit Optimal Binary Pebbling for One-Way Hash Chain Reversal

Last updated Saturday, 24-Nov-2018 12:15:56 CET by Berry Schoenmakers.

Now available: paper Binary Pebbling Algorithms for In-Place Reversal of One-Way Hash Chains from Nieuw Archief voor Wiskunde, September 2017 issue, in which the main results of the FC 2016 paper are highlighted, with illustrations.

Also available: Financial Crypto 2016 slides.

Sample code using the SHA-256 hash function

The paper (IACR eprint 2014/329) presents pseudocode for three novel algorithms for hash chain reversal:

In-place Jakobsson's speed-2 binary pebbles
In-place optimal binary pebbles
Fast optimal binary pebbles

Algorithm 3 maximizes speed at the expense of some additional storage, which is of interest when the hash function is implemented in hardware (e.g., using Intel's AES-NI).

The sample programs below print the length-2^k hash chain with default seed value x = "" (empty input) in reverse.

In-place implementation of Jakobsson's speed-2 pebbles
In-place implementation of optimal binary pebbles
Fast implementation of optimal binary pebbles

Programs are available in Python, C (plain ANSI C, compile with e.g. gcc -O3 -lcrypto), and Java. The code closely follows the pseudocode in the paper. Note that the programs start out computing the hash chain in the forward direction, and then loop outputting the reversed hash chain one element at a time.

For downloadable code, see src/readme.txt.

Sample output for k = 3:

30edbc354e8cf656adcddbeefbf3f5073372cdc42e4eca2e797bda8abebb6a05
06adb8ba851d855951490003c3c1fe4d3a2e6cd87a1299208ddfd3949d131657
1bee5a29daf06786a5516d9226b30bbdbf422a7ed475e42c3f930ea04c612091
9ff42bc5a042d3c79a61d7cb6769408fe13b1e5fc30e01e19a100e79109ed688
75d7682c8b5955557b2ef33654f31512b9b3edd17f74b5bf422ccabbd7537e1a
aa6ac2d4961882f42a345c7615f4133dde8e6d6e7c1b6b40ae4ff6ee52c393d0
5df6e0e2761359d30a8275058e299fcc0381534545f55cf43e41983f5d4c9456
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

In-place Jakobsson's speed-2 pebbles

Python code:

# In-place speed-2 pebble P_k
# Copyright (C) 2014 Berry Schoenmakers
import hashlib
k=input()
z=[]; q=k; y=hashlib.sha256("").digest()
for h in xrange(1<<k,1,-1):
    if h==1<<q: z.insert(0,y); q-=1
    y=hashlib.sha256(y).digest()
print str(y).encode('hex')
for r in xrange((1<<k)-1,0,-1):
    print str(z[0]).encode('hex')
    c=r
    i=0
    while ~c&1: z[i]=z[i+1]; i+=1; c>>=1
    i+=1; c>>=1
    q=i-1
    while c: 
        z[q]=hashlib.sha256(z[i]).digest()
        if q!=0: z[q]=hashlib.sha256(z[q]).digest()
        while ~c&1: i+=1; c>>=1
        while c&1: i+=1; c>>=1
        q=i

C code:
/* In-place speed-2 pebble P_k */ /* Copyright (C) 2014 Berry Schoenmakers */ #include <stdio.h> #include <openssl/sha.h> #include <string.h> void main(void) { char k; scanf("%d",&k); unsigned char y[32]; SHA256(y,0,y); unsigned char z[k][32]; char q=k; int h=1<<k; for (;q;h--) { if (h==1<<q) {q--; memcpy(z[q],y,32);} SHA256(y,32,y); } char e=0; for (;e!=32;e++) printf("%02x",y[e]); printf("\n"); int r=(1<<k)-1; for (;r;r--) { e=0; for (;e!=32;e++) printf("%02x",z[0][e]); printf("\n"); int c=r; char i=0; for (;~c&1;c>>=1) {memcpy(z[i],z[i+1],32); i++;} i++; c>>=1; q=i-1; while (c) { SHA256(z[i],32,z[q]); if (q) SHA256(z[q],32,z[q]); for (;~c&1;c>>=1) i++; for (;c&1;c>>=1) i++; q=i; } } }

Java code:
/* In-place speed-2 pebble P_k */ /* Copyright (C) 2014 Berry Schoenmakers */ import java.security.MessageDigest; public class PebblingS2 { public static void main(String[] args) throws Exception { MessageDigest sha256 = MessageDigest.getInstance("SHA-256"); byte k=Byte.parseByte(args[0]); byte[] y=sha256.digest(); byte[][] z=new byte[k][]; byte q=k; int h=1<<k; for (;q!=0;h--) { if (h==1<<q) {q--; z[q]=y;} y=sha256.digest(y); } for (byte e=0;e<32;e++) System.out.print(String.format("%02x",y[e])); System.out.println(); for (int r=(1<<k)-1;r!=0;r--) { for (byte e=0;e<32;e++) System.out.print(String.format("%02x",z[0][e])); System.out.println(); int c=r; byte i=0; for (;(c&1)==0;c>>=1) {z[i]=z[i+1]; i++;} i++; c>>=1; q=(byte)(i-1); while (c!=0) { z[q]=sha256.digest(z[i]); if (q!=0) z[q]=sha256.digest(z[q]); for (;(c&1)==0;c>>=1) i++; for (;(c&1)==1;c>>=1) i++; q=i; } } }} <

In-place optimal binary pebbles

Python code:

# In-place optimal pebble P_k
# Copyright (C) 2014 Berry Schoenmakers
import hashlib
k=input()
z=[]; q=k; y=hashlib.sha256("").digest()
for h in xrange(1<<k,1,-1):
    if h==1<<q: z.insert(0,y); q-=1
    y=hashlib.sha256(y).digest()
print str(y).encode('hex')
for r in xrange((1<<k)-1,0,-1):
    print str(z[0]).encode('hex')
    c=r
    i=0
    while ~c&1: z[i]=z[i+1]; i+=1; c>>=1
    i+=1; c>>=1
    m=i; s=0;
    while c: 
        l=i
        while ~c&1: i+=1; c>>=1
        j=r&((1<<i)-1)
        p=i&1^j&1
        h=p+j*(i-m)+(m+3-l)*(1<<l)-(1<<m)>>1
        q=h.bit_length()-1
        for _ in xrange(p+i+1-s>>1):
            y=z[q]
            if h==1<<q: q-=1
            z[q]=hashlib.sha256(y).digest()
            h-=1
        m=i; s=m+1
        while c&1: i+=1; c>>=1

C code:
/* In-place optimal pebble P_k */ /* Copyright (C) 2014 Berry Schoenmakers */ #include <stdio.h> #include <openssl/sha.h> #include <string.h> char bitlen(int h) {char q=0; for (;h;h>>=1) q++; return q;} void main(void) { char k; scanf("%d",&k); unsigned char y[32]; SHA256(y,0,y); unsigned char z[k][32]; char q=k; int h=1<<k; for (;q;h--) { if (h==1<<q) {q--; memcpy(z[q],y,32);} SHA256(y,32,y); } char e=0; for (;e!=32;e++) printf("%02x",y[e]); printf("\n"); int r=(1<<k)-1; for (;r;r--) { e=0; for (;e!=32;e++) printf("%02x",z[0][e]); printf("\n"); int c=r; char i=0; for (;~c&1;c>>=1) {memcpy(z[i],z[i+1],32); i++;} i++; c>>=1; char m=i; char s=0; while (c) { char l=i; for (;~c&1;c>>=1) i++; int j=r&((1<<i)-1); char p=i&1^j&1; int h=p+j*(i-m)+(m+3-l)*(1<<l)-(1<<m)>>1; char q=bitlen(h)-1; char d=p+i+1-s>>1; for (;d--;h--) { unsigned char* y=z[q]; if (h==1<<q) q--; SHA256(y,32,z[q]); } m=i; s=m+1; for (;c&1;c>>=1) i++; } } }

Java code:
/* In-place optimal pebble P_k */ /* Copyright (C) 2014 Berry Schoenmakers */ import java.security.MessageDigest; public class PebblingS { public static void main(String[] args) throws Exception { MessageDigest sha256 = MessageDigest.getInstance("SHA-256"); byte k=Byte.parseByte(args[0]); byte[] y=sha256.digest(); byte[][] z=new byte[k][]; byte q=k; int h=1<<k; for (;q!=0;h--) { if (h==1<<q) {q--; z[q]=y;} y=sha256.digest(y); } for (byte e=0;e<32;e++) System.out.print(String.format("%02x",y[e])); System.out.println(); for (int r=(1<<k)-1;r!=0;r--) { for (byte e=0;e<32;e++) System.out.print(String.format("%02x",z[0][e])); System.out.println(); int c=r; byte i=0; for (;(c&1)==0;c>>=1) {z[i]=z[i+1]; i++;} i++; c>>=1; byte m=i; byte s=0; while (c!=0) { byte l=i; for (;(c&1)==0;c>>=1) i++; int j=r&((1<<i)-1); byte p=(byte)(i&1^j&1); h=p+j*(i-m)+(m+3-l)*(1<<l)-(1<<m)>>1; q=(byte)(31-Integer.numberOfLeadingZeros(h)); for (byte d=(byte)(p+i+1-s>>1);d!=0;d--) { y=z[q]; if (h==1<<q) q--; z[q]=sha256.digest(y); h--; } m=i; s=(byte)(m+1); for (;(c&1)==1;c>>=1) i++; } } }}

Optimal binary pebbles optimized for speed

Python code:

# Optimal pebble P_k, optimized for speed
# Copyright (C) 2014 Berry Schoenmakers
import hashlib
k=input()
z=[]; q=k; y=hashlib.sha256("").digest()
for h in xrange(1<<k,1,-1):
    if h==1<<q: z.insert(0,y); q-=1
    y=hashlib.sha256(y).digest()
print str(y).encode('hex')
a=[None]*(k>>1); v=0
for r in xrange((1<<k)-1,0,-1):
    print str(z[0]).encode('hex')
    c=r
    i=0
    while ~c&1: z[i]=z[i+1]; i+=1; c>>=1
    i+=1; c>>=1
    if c&1: a[v]=(i,0); v+=1
    u=v
    w=(r&1)+i+1
    while c: 
        while ~c&1: w+=1; c>>=1
        u-=1; q,g=a[u]
        for _ in xrange(w>>1):
            y=z[q]
            if g==0: q-=1; g=1<<q
            z[q]=hashlib.sha256(y).digest()
            g-=1
        if q!=0: a[u]=(q,g)
        else: v-=1
        w=w&1
        while c&1: w+=1; c>>=1

C code:
/* Optimal pebble P_k, optimized for speed */ /* Copyright (C) 2014 Berry Schoenmakers */ #include <stdio.h> #include <openssl/sha.h> #include <string.h> void main(void) { char k; scanf("%d",&k); unsigned char y[32]; SHA256(y,0,y); unsigned char z[k][32]; char q=k; int h=1<<k; for (;q;h--) { if (h==1<<q) {q--; memcpy(z[q],y,32);} SHA256(y,32,y); } char e=0; for (;e!=32;e++) printf("%02x",y[e]); printf("\n"); typedef struct {char q; int g;} pebble; pebble a[k>>1]; char v=0; int r=(1<<k)-1; for (;r;r--) { e=0; for (;e!=32;e++) printf("%02x",z[0][e]); printf("\n"); int c=r; char i=0; for (;~c&1;c>>=1) {memcpy(z[i],z[i+1],32); i++;} i++; c>>=1; if (c&1) {a[v]=(pebble){i,0}; v++;} char u=v; char w=(r&1)+i+1; while (c) { for (;~c&1;c>>=1) w++; u--; pebble P=a[u]; char d=w>>1; for (;d--;P.g--) { unsigned char* y=z[P.q]; if (!P.g) {P.q--; P.g=1<<P.q;} SHA256(y,32,z[P.q]); } if (P.q) a[u]=P; else v--; w=w&1; for (;c&1;c>>=1) w++; } } }

Java code:
/* Optimal pebble P_k, optimized for speed */ /* Copyright (C) 2014 Berry Schoenmakers */ import java.security.MessageDigest; public class PebblingW { public static void main(String[] args) throws Exception { MessageDigest sha256 = MessageDigest.getInstance("SHA-256"); byte k=Byte.parseByte(args[0]); byte[] y=sha256.digest(); byte[][] z=new byte[k][]; byte q=k; int h=1<<k; for (;q!=0;h--) { if (h==1<<q) {q--; z[q]=y;} y=sha256.digest(y); } for (byte e=0;e<32;e++) System.out.print(String.format("%02x",y[e])); System.out.println(); class Pebble {byte q; int g;} Pebble[] a = new Pebble[k>>1]; byte v=0; for (int r=(1<<k)-1;r!=0;r--) { for (byte e=0;e<32;e++) System.out.print(String.format("%02x",z[0][e])); System.out.println(); int c=r; byte i=0; for (;(c&1)==0;c>>=1) {z[i]=z[i+1]; i++;} i++; c>>=1; if ((c&1)==1) {a[v]=new Pebble(); a[v].q=i; v++;} byte u=v; byte w=(byte)((r&1)+i+1); while (c!=0) { for (;(c&1)==0;c>>=1) w++; u--; Pebble P=a[u]; for (byte d=(byte)(w>>1); d!=0; d--) { y=z[P.q]; if (P.g==0) {P.q--; P.g=1<<P.q;} z[P.q]=sha256.digest(y); P.g--; } if (P.q!=0) a[u]=P; else v--; w=(byte)(w&1); for (;(c&1)==1;c>>=1) w++; } } }}