Funkspiel Schemes: An Alternative to Conventional Tamper ResistanceJ. Håstad
J. Jakobsson
A. Juels
M. Yung
Royal Inst. of Technology, Stockholm
RSA Laboratories
RSA Laboratories
Certco
Funkspiel Schemes: An Alternative to Conventional Tamper Resistance
J. Håstad
J. Jakobsson
A. Juels
M. Yung
Royal Inst. of Technology, Stockholm
RSA Laboratories
RSA Laboratories
Certco
Captured by Germans, along with radio and three message/ciphertext pairs Lauwers worked as radio operator for SOE, British underground during WW II
Germans sought to mount “Funkspiel”, i.e., pass false messages to SOE Lauwers SOE made use of a kind of MAC
Subverting the Funkspiel
…………....stop…..
Message 1: Message 2: …………....stop…..
Message 3: ………….……..…..
o
o
u e Claimed that “MAC” involved corruption of ‘o’ in stop 16th letter Germans demanded to know “MAC”
Lauwers had been instructed to introduce an error into 16th letter of every message as “MAC”
Lauwers made clever observation about his three messages:
Subverting the Funkspiel
Germans were deceived
Allies were deceived
Modern cryptographer’s view
Alice Bob Eve (Enemy)
Funkspiel scheme
Alice Bob Eve
Step 1: Alice sends messages to Bob
Alice Bob Eve message1, MAC (message1) message2, MAC (message2) message3, MAC (message3)
Step 2: Alice changes key (maybe)
Alice
Step 3: Eve steals Alice’s key
Alice
Step 4: Eve impersonates Alice
Bob Eve “I love you”, MAC (“I love you”)
Step 5: Bob determines whether Alice changed key
MAC (“I love you”) She loves me?
She loves me not?
What do we want?
Eve can’t tell whether Alice changed key
Even though Eve has seen MAC(message1), MAC(message2),...
Bob can tell whether Alice changed key
Related work
Forward-secure signature schemes
Attacker knows that key evolves
Distress PIN
No security against eavesdropper
Deniable encryption
A funkspiel scheme
MAC key 0: MAC key 1: 0 1 1 0 1 0 1 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 Problems: We need one bit for every MAC;
Eve can cheat with small probability ???
Another funkspiel scheme (simplified)
Problem: What if Eve sees Bob’s keying material?
She can forge a MAC h h ??? ??
Asymmetric funkspiel scheme
PKA SKA PKB SKB EPK_B(SigSK_A[message]) PKA SKA ???
Asymmetric funkspiel scheme
Semantically secure encryption (e.g., El Gamal) ensures that Eve can’t test signature against SK
Key swap for Alice under El Gamal is efficient, e.g., she can randomize last 100 bits
If Eve sees Bob’s keys, she still can’t forge MAC
Scheme is less efficient than symmetric ones
Real-world funkspiel
Alice changes key when she senses Eve is attempting to break in (no coin flipping)
Bob tries to determine whether Alice sent “distress signal”, i.e., changed key
What this good for?
Funkspiel schemes permit detection and tracing
Funkspiel schemes can give false sense of security or success to attacker
E.g., cash card
Tamper resistant hardware
Currently uses “zeroization”
Comments