What is Cryptography?
The cores of cryptography are:
- Secret key establishment
- Secure communication
Beyond the basic:
- Digital signature
- Anonymous communication
- Anonymous digital cash: OK to spend once, identify uncovered for double spending.
- Secure multi-party computation without trusted auth.
- Zero knowledge
A symmetric cipher is defined over : .
E is always randomized, while
D is deterministic.
The One Time Pad
Information Theoretic Security
(Shannon 1949): Cipher Text should reveal no “info” about Plain Text.
DEF: A cipher (E, D) over has perfect secrecy if and where k is unified distributed in
Lemma: OTP has perfect secrecy if key length message length.
Pseudo Random Generator
We can use pseudo random generator, aka PRG: use a seed to generate the key to avoid sending the key with longer length than the message:
and n s
The stream cipher use the pseudo random pad instead of OTP, it does NOT have perfect secrecy, but might be secure enough if PRG is unpredictable.
- The hacker can predict some part of the message, to get the key
- Then predict the key to cover the remaining text.
The PRG is predictable if the chance to predict the bit is larger than . The determines how hard and how much data needs to be collected to launch the attack, — it should be polynomial .
Do not use glibc random for crypto!
Attacks on Stream Cipher
Use OTP twice is dangerous:
- Project Venona (1941 - 1946)
WEP uses 24bit
IV concatenated with private
k to encrypt the message:
- the key is rotated after 16M messages
- and the key is incremented by one for each key, and PRG(RC4) will generate the same pad for related keys. It only take 10^6 frames to detect k!
No integrity! The attacker can apply on cipher text to mutate the plain text!
Uses a statistical test,
A and the , the Advantage is defined as:
Adv is close to 0,
A and PRG are not distinguishable.
The PRG is secure if the existing efficient statistical test A, and
Adv is negligible.
Use Shannon’s idea with relaxation, , and the two distributions are computation non-distinguishable.