User:Kosniaz/Cryptography And Randomness

Randomness and One-way functions

The concept of randomness is very important in cryptography, as in many cases generation of random strings is required (e.g. nonce,salt,one time pad).

Pseudorandom Generator

Consider the One Time Pad:

• Gen : generates a random key k from $\{0,1\}^{n}$
• Enc:$c=m\oplus G(k)$
• Dec:$m=c\oplus G(k)$

One of the problems we encounter when implementing the OTP is that we need to generate a random k that is as long as the message. Since longer random values are harder to create, we can use a pseudorandom generator, to extend a smaller random value.

A Pseudorandom Generator is a *Deterministic* function that takes a truly random seed (short string - key) and extends it "randomly". We notate that the extended key has length l(n), where n is the length of the seed. We use it PSG because in some cryptosystems we need long keys, but it is impractical to generate randomly so large keys. See below for an example of a cryptosystem that makes use of a pseudorandom generator.

Pseudorandom Function

Not to be confused with the PSG defined above, a pseudorandom function is a keyed function that is (computationally) indistinguishable from a random oracle, for an adversary that doesn't have the key. Blum blum shub and RC4 are two famous pseudorandom generators.

One-way functions/permutations

Some functions are computationally hard to invert. The following test validates if a function is one-way:

<must insert test>

Factorization, subset sum, and discrete log are some one-way functions.

Hard-core predicates

Hard-core predicates are predicates that prove that a function is one-way. They are predicates on the function's input. The value of a hard-core predicate h(x) is easy to calculate given x, but hard given f(x). Actually it is as hard as finding x from f(x). It can be proven that every one-way function, can be slightly transformed into a one-way function with a hard-core predicate.

Key streching

Takes a key and makes it longer, in order to make it harder for an adversary to find it by brute-force means. How? An adversary has to test every key in a much larger keyspace, or either test every key in the initial (small) keyspace but with a significant cost in every transformation. How do we do that?

PBKDF2

$DK=T1||T2||...||T_{dklen/hlen}$ Ti = F(Password, Salt, c, i) where F(Password, Salt, c, i) = U1 ^ U2 ^ ... ^ UC

U1 = PRF(Password, Salt || INT_32_BE(i)) U2 = PRF(Password, U1) ... Uc = PRF(Password, Uc-1)

for more check this

PBKDF2 applies a pseudorandom function, such as a cryptographic hash, cipher, or HMAC to the input password or passphrase along with a salt value and repeats the process many times to produce a derived key, which can then be used as a cryptographic key in subsequent operations. The added computational work makes password cracking much more difficult, and is known as key stretching.

Having a salt added to the password reduces the ability to use precomputed hashes (rainbow tables) for attacks, and means that multiple passwords have to be tested individually, not all at once. The standard recommends a salt length of at least 64 bits.

Hash function

Hash functions (συναρτήσεις καταρματισμού ή συναρτήσεις σύνοψης) are easily computable functions that compress their input into strings of shorter (usually fixed) length. We may call a function collision-resistant/freeness depending on the result of the following test:

Now, consider a family of hash functions,which we define as a function $H^{S}(x)=H(s,x)$, where s is a key that we use to generate the hash values. With this in mind, we may formally define a hash function.

Definition 1: Hash function

We define a hash function as a pair of PPT Algorithms (Gen, H) so that

• Gen will take $1^{m}$ as input and produce a key s
• There exists a polynomial l(n) so that $H(s,x)(x\epsilon \{0,1\}*)$ returns a string

in $\{0,1\}^{l(n)}$.

Definition 2: Collision-resistance game

Given a hash function Π=(Gen,H), an adversary A, and a safety parameter n the game is as follows.

• Gen generates a key, in respect to the parameter n.
• $\mathrm {A}$ is given the key s and returns strings x and x'
• The result is 1 if x<>x' and $H^{S}(x)=H^{S}(x')$, 0 otherwise.

Using the above game we can guarantee or disprove the collision-freeness of a hash function.

Some desired properties of a hash function:

• preimage resistance
• 2nd preimage resistance
• collision resistance/freeness
• Perturbation (it's hard to find x,x' so that $hamming(H(x),H(x'))<\epsilon$)
• Range (it's hard given y, and ε to find x so that $y\leq H(x)<y+\epsilon$)

Example of hash functions :

• md5 (not cryptographically safe)
• sha-1 (not cryptographically safe)
• sha-2 family (safe!)

Birthday Paradox

(Under construction)

Applications of Hashing

• Binding
• Timestamping
• Password storage/User authentification (some cool anti-hacking trix implemented here!)
• Proof of work
• Content Validation (Merkle Trees)

MAC

We use macs to achieve authentification and data-integrity check. We find it necessary to prove that a message we receive has not been tampered with. To do that we use a tuple of algorithms (Gen,Mac,Vrfy) so that

• Gen() takes $1^{n}$ and returns a key k, $|k|\geq n$
• Mac() takes k and a message m and returns t.
• Vrfy() is a (deterministic) algorithm takes k,m and t and returns 1 if t is valid, else 0.

Definition 3: Existential unforgeability under an adaptive chosen-message attack

Consider a set of MAC algorithms. We say that our authentification is existentially unforgeable under an adaptive chosen-message attack when an adversary cannot win a game called Mac-Forge, except for with negligible probability.

Definition 4: MAC-forge game

• Gen generates a random key.
• Adversary A, who knows n (safety parameter) has access to oracle Mac_k(), with which he/she mac's

a set Q of m's. Then he outputs an (m,t).

• Result is 1 iff Vrfy_k(m,t)=1 and m isn't in Q.

Repetition attacks

Adv can resend older <m,t> pairs which ,naturally, would be accepted by the receipient. But that can be stopped if we always send a unique message id or a timestamp in every message.

How we generate MAC's

PseudoRandomFunction

if we use a PRF as the mac() algorithm, and if we test the output of the mac() algorithm and compare it to t in vrfy() then we have achieved existential unforgeability under an adaptive chosen-message attack.

MAC:Arbitrary length of message m

We extend our MAC algorithms so that we can use it with arbitrarily lengthed messages m. There are several ideas out there that seem good, but disappoint under close study. A truly good extension of a MAC is as follows.

We have Π'=(Gen',Mac',Vrfy'). Consider the following MAC:

<mac test>

Theorem 4

In the above described MAC, if Π' Existential unforgeability under an adaptive chosen-message attack, then the resulting MAC has Existential unforgeability under an adaptive chosen-message attack

MAC combined with Cryptosystems

Safety of a combination: Authenicated communication

• Authentication-and-encryption scheme
• Encryption-then-authentication scheme
• Authentication-then-encryption scheme