Bitcoin and Cryptocurrency Technologies

KR-security and PRF-security (KR-key recovery; PRF-pseudo random function). PRF security as our main metric. If E is PRF-secure then it is KR-secure

DES

Birthday Attack
DES Key length k=56 Block length l=64
“(EKS) Exhaustive key search attack power(2,55) DES computations” “power(2, 32)“
“Differential cryptanalysis attack (1992) running time power (2,47)“
“Linear cryptanalysis (1993) running time power(2,44)“
EKS can be performed in parallel. Wiener designed DES-cracking machine in 1993 that finds key in 3.5 hours
DES is considered broken because its short key size permits rapid key-search. But DES is a very strong design as evidenced by the fact that there are no practical attacks that exploit its structure
“2DES, 3DES and Meet in the middle attack” “power(2, 32)“

AES (replaces DES in 2001)

“DES, AES are good block ciphers in the sense that they are PRF-secure up to the inherent limitations of the birthday attack and known key-recovery attacks. But beware that the future may prove these assumptions wrong!”

- How do we encrypt a long message using a primitive that only applies to n-bit blocks.

ECB - Electronic Codebook Mode - For encryption to be secure it must be randomized. Clasically, encryption is a code, associating to each message a unique ciphertext. Now we are saying no such code is secure, and we look to encryption mechanisms which associate to each message a number of different possible ciphertexts.
CBC$ - Cipher Block Chaining with random IV (initialization vector) mode - E must be blockcipher
CTR$ mode - Counter with random IV mode. E is not required to be a blockcipher. Encryption and Decryption are parallelizable.

IND-CPA: indistinguishability under chosen plaintext attack
CTR$ can be broken (in the IND-CPA sense) in about power(2, n/2) queries, where n is the block length of the underlying block cipher, regardless of the cryptanalytic strength of the block cipher.

- collision-resistant (CR) data compression/transformation, practical hash functions like MD5, SHA1, SHA256, SHA3, ? are keyless. Application: Password verification; Compare by hash; Virus protection.”
MD5 “2005, 2006 attack by [WaFeLaYu, LeWadW, KI] in 1 minute”

SHA1 “No collisions for SHA1 have yet been publicly announced. But collisions were found for the compression function sha1 of SHA1 in 2015. We expect collisions for SHA1 to be found and announced soon. Google, Microsoft and Mozilla browsers will stop accepting SHA1-based certificates in 2017.”

SHA256

q-trial birthday attach finds a collision with probability about q^2/2^(n+1). So a collision can be found in about q=sqrt(2^(n+1))=2^(n/2) trials

“MD transform - Merkle?Damg†rd construction is used in MD5, SHA1, SHA2”

compression functions

basic CBC MAC is not UF-CMA (unforgeable under chosen message attack) secure due to the splicing attack.
preventing Replay attack using Timestamp or Counters
Any PRF is a MAC

FIL - fixed input length
VIL - variable input length

• MAC
• DES_ECBC_MAC
• AES_ECBC_MAC
• AES_ECBC_MAC
• HMAC-SHA1
• HMAC-SHA256
• CMAC

“HMAC is one of the most widely standardized and used cryptographic constructs: SSL/TLS, SSH, IPSec, FIPS 198, IEEE 802.11, IEEE 802.11b, ?”

Goal Primitive Security notion
Data privacy symmetric encryption IND-CPA
Data authenticity MAC UF-CMA

INT-CTXT: integrity of ciphertext

Generic Composition - order matters
Method Usage
Encrypt-and-MAC (E&M) SSH “IND-CPA, INT-CTXT = no, no”
MAC-then-encrypt (MtE) SSL/TLS “yes, no”
Encrypt-then-MAC (EtM) IPSec “yes, yes”

AEAD - Authenticated Encryption with Associated Data

• CCM
• GCM
• OCB
• ECB

No clear winner. What performance do I need? Single or multiple keys? Patents ok or not? Do I need to comply with some standard?

- stateful generators

INDR : Indistinguishablity from random
Forward secure PRG
“In practice, random number generation involves Seeding and PRG. In principle, we know how to design good PRGs, but seeding remains a problem. Typical methods: entropy pool; hardware RNGs.”

DH secret key exchange (Diffie and Hellman)
Discrete Logrithm Problem
CDH problem - computational Diffie?Hellman problem is the assumption that a certain computational problem within a cyclic group is hard.
KEM - key encapsulation mechanisms
(EG) ElGamal encryption system - the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie?Hellman key exchange.

• EG KEM
• DHIES - Discrete Logrithm Integrated Encryption Scheme
• ECIES - Elliptic Curve Integrated Encryption Scheme
• RSA OAEP - Optimal asymmetric encryption padding

RSA is one of the first practical public-key cryptosystems and is widely used for secure data transmission “RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1978”
“If RSA is 1-way and H, G are random oracles then ? OAEP is IND-CPA secure [BR94] ? OAEP is IND-CCA secure [FOPS00]”

Step 1: key generation Alice lets (pk,sk) $ ? K and stores sk (securely).
Step 2: pk dissemination Alice enables any potential verifier to get pk.
Step 3: sign Alice can generate a signature å of a document M using sk.
Step 4: verify Anyone holding pk can verify that å is Alice?s signature on M.”

PSS - Probabilistic Signature Scheme. PSS was speciffically developed to allow modern methods of security analysis to prove that its security directly relates to that of the RSA problem.
“ElGamal, DSA/ECDSA, Schnorr”

Man-in-the-middle attack

PKI usually done via certificates

Certificate Process:

• Alice generates pk and sends it to CA
• CA does identity check
• Alice proves knowledge of secret key to CA
• CA issues certificate to Alice
• Alice sends certificate to Bob
• Bob verifies certificate and extracts Alice's pk

CRL - Certificaterevocation lists. Revocation is a big problem and one of the things that is holding up
“In PGP, ther eare no CAs.”

“Session Key Distribution protocols used ubiquitously: SSL, TLS, SSH, IPSEC, 802.11, ?”

Forward secrecy
Preventing dictionary attacks: avoiding image revelation. Example: protocol KE4

Internet Casino: Protocol G3 - Commitment Schemes (hiding and binding)
Flipping a common coin: Protocol CF2
“Key exposure prevention - Distribution (sharing): Threshold signatures; Key evolution: Forward security,”

• Internet Casino
• Commitment
• Shared coin flips
• Threshold cryptography
• Forward security
• Program obfuscation
• Zero-knowledge
• Certified e-mail
• Identity-based encryption
• Fully-homomorphic encryption
• Searchable encryption
• Oblivious transfer
• Secure computation
• Group signatures
• Aggregate signatures
• Electronic voting
• Auctions

Bitcoin and Cryptocurrency Technologies

Georgia Tech OMS (Online Master's Program) Cyber Security Class. Wenke Lee is a great professor.