If you remember the Onetime pad (OTP), we had a message m
of length
n
and a pad p
of length n
and we computed the ciphertext c
by
computing c = m \xor p
for all n
bits.
However, it's very hard to come up with the pad.
TODO: transmitting a secert as long as the message is equivalent to transmitting the message
pseudorandom generator G

key or seed >  G  > pad

{0,1}^n {0,1}^l(n)
l(n) > n
Definition: G
is a pseudorandom generator (PRG) if no adversary can
distinguish between a string x
drawn randomly from {0,1}^l(n)
(ideal situation) and the output of the program G(s)
,
where s < {0,1}^n
with probability better than 1/2 + negl(n)
negl(n)
is a function that goes to zero faster than any
inverse polynomial function of n
Stream cipher is a PRG
K
from shortterm key (nonce)May be counter based:

 i  < + 1


\ /
.

k > G 


\ /
.
Output
pad
May be state based:
<\
 \
 state  next state fn f 
 
\/

\ / initial state
. is the key K

 G 


\ /
.
output bytes
N
bytes: Z_n = {0, 1, ..., N1}
(All math is mod N
). Default N = 256
i
and j
S
of Z_n
S
from key K
RC4PRG:
RC4_PRG():
i = i + 1 // update state
j = j + S[i]
Swap(S[i], S[j])
z = S[S[i]+S[j]] // generate output
return z
RC4KSA (key K = L
values on N
bits (k = L
bytes when N = 256
)):
RC4_KSA(k):
S[0 ... N1] = [0 ... N1]
j = 0
for i = 0; to N1:
j = j + S[i] + K[i mod L]
Swap(S[i], S[j])
i = j = 0
Vulnerabilities:
=>
distinguishersS
)G
Code:
SPRITZ_PRG():
i = i + w
j = k + S[j + S[i]]
k = i + k + S[j]
Swap(S[i], S[j])
z = S[j + S[i + S[z+k]]]
return z
w
is always relatively prime to N
z
is used as feedback (see line before return z
)Initialization:
S
is the identity permutationi = j = k = 0
z = 0
a
set to 0w
is initialized to 1Code:
SQUEEZE(r):
if a > 0:
SHUFFLE()
P = new array of size r
for v = 0 to r1
p[v] = SPRITZ_PRG
return p
ENCRYPT(k, m):
KEYSETUP(K)
C = M + SQUEEZE(M.length)
return C
KEYSETUP(k):
InitializeState()
ABSORB(k)
Absorb
takes an arbitrary sequence of k
bytes as input Spritz can also be used as a hash function!
Nice and simple designs

512 bit state 


 <
 
ChaCha 
 
 
 + 


\ /
.
State is 4 x 4 x 32 bit
matrix, each cell indexed from 0, ..., 15
c  c  c  c constant 128bit
   
k  k  k  k key 256bit
   
k  k  k  k
   
n  n  n  n nonce counter 128bit
It's called ChaCha20 because it has 20 rounds, broken up into quarter rounds (QRs).
This is a style of design called ARX design: Additions, Rotations and XOR
Code:
QR(a,b,c,d):
a += b; d ^= a; d <<<= 16
c += d; b ^= c; b <<<= 12
a += b; d ^= a; d <<<= 8
c += d; b ^= c; b <<<= 7
You can imagine applying this to a column of this matrix.
Round 1:
QR(0, 4, 8, 12) # the first column
QR(1, 5, 9, 13)
QR(2, 6, 10, 14)
QR(3, 7, 11, 15)
Round 2
QR(0, 5, 10, 15) # the main diagonal
QR(1, 6, 11, 12) # just above the main diagonal
QR(2, 7, 8, 13)
QR(3, 4, 9, 14)
Round 1 and round 2 are a double round
ChaCha20 has 10 double rounds