10b-SymmetricStream

https://en.wikipedia.org/wiki/Stream_cipher
A stream cipher is a symmetric key cipher.
Plain-text digits are combined with a pseudo-random cipher digit stream (key-stream).
The pseudo-random key-stream is typically generated serially.
The generation starts from a random seed value,
using digital shift registers.
A shift register is a cascade of flip flops,
sharing the same clock,
The output of each flip-flop connects to the ‘data’ input,
of the next flip-flop in the chain,
resulting in a circuit that shifts by one position,
the ‘bit array’ stored in it,
‘shifting in’ the data present at its input,
and ‘shifting out’ the last bit in the array,
at each transition of the clock input.
10b-SymmetricStream/stream.jpg

Processes input elements continuously.
The key is input to a pseudo-random bit generator.
Process produces a stream of random-like numbers.
XOR key-stream output with plain-text bytes.
Should be unpredictable,
without knowing input key.

1.1.1 Steam Cipher Structure

Like with 06-OneTimePad.html using unique one time binary pad as the key,
but use a key stream instead:
10b-SymmetricStream/06.png

1.1.2 Relative Speed of Symmetric Ciphers

1.1.3 RC4 Algorithm

1.1.3.1 1. Key-scheduling algorithm

Key-scheduling is not the encryption process yet.
It’s just preparation, creating a seeded random array.

For i in state:
Mix key (K), one byte at a time (K[i]),
with the initial state array S[i].
j is a running index, starting at 0,
jumping around pseudo-randomly after.
Each time j is computed:
j = j + key[i] + S[i] % 256
resulting in some random position in the array.
S[j] is set to that value.
Each step:
10b-SymmetricStream/pasted_image001.png

Key may be shorter than 255.
It wraps around during scheduling.
swap(S[i], S[j])
10b-SymmetricStream/pasted_image002.png

If you run out of key bytes,
then you just wrap around, on the key.
All key indices are mod (%) key length.
RC4 accepts keys from anywhere between 1 and 256 bytes long.
Usually, 128 bit (16 byte) keys are used,
which means that each byte in the key is used 16 times.

Goal is to make a mess of the data,
rolling forward though scheduling.
Without the key,
the numbers should not be not feasibly predictable.
With the key, they are repeatable.

1.1.3.2 2. Pseudo-random stream generating algorithm

Here we actually start the key-generation.
This is the primary work behind encryption for a stream cipher.

Perturb state repeatedly
For each byte of a random byte-stream needed (i in 255 below):
where j starts at 0,
j = j + S[i] % 256
swap(S[i], S[j])
10b-SymmetricStream/pasted_image002.png

The lookup stage of RC4
The output byte is selected by looking up the values of S[i] and S[j],
adding them together modulo 256,
and then using the sum as an index into S;
S(S[i] + S[j]) is used as a byte of the key stream, K.
Key is S[k].
k = S[S[i] + S[j] % 256]
10b-SymmetricStream/pasted_image003.png

Generate limitless numbers of k bytes.

#!/usr/bin/python3
# -*- coding: utf-8 -*-

from itertools import cycle
from typing import List, Generator

# Key preparation:
def key_schedule(key: str) -> List[int]:
    state_array = list(range(256))
    key_bytes = cycle(ord(x) for x in key)
    j = 0
    for i in range(256):
        j = (j + state_array[i] + next(key_bytes)) % 256
        state_array[i], state_array[j] = state_array[j], state_array[i]
    return state_array

# Keystream generator:
def pseudorandom_generator(state_array: List[int]) -> Generator[int, None, None]:
    j = 0
    for i in cycle(range(256)):
        j = (j + state_array[i]) % 256
        state_array[i], state_array[j] = state_array[j], state_array[i]
        k = (state_array[i] + state_array[j]) % 256
        yield state_array[k]

def main() -> None:
    plaintext = "secret"
    print(f"Plaintext is: {plaintext}\n")

    # encrypt
    print("Encrypting now, one byte at a time:")
    key = "not-so-random-key"
    state_array = key_schedule(key)
    infinite_key_generator = pseudorandom_generator(state_array)
    translate_array = []
    for c in plaintext:
        print("%02X" % (ord(c) ^ next(infinite_key_generator)))
        translate_array.append("%02X" % (ord(c) ^ next(infinite_key_generator)))
    ciphertext = "".join([chr(int(c, 16)) for c in translate_array])
    print(f"\nCiphertext is: {ciphertext}\n")

    # decrypt
    print("Decrypting now, one byte at a time:")
    key = "not-so-random-key"
    state_array = key_schedule(key)
    infinite_key_generator = pseudorandom_generator(state_array)
    translate_array = []
    for c in ciphertext:
        print("%02X" % (ord(c) ^ next(infinite_key_generator)))
        translate_array.append("%02X" % (ord(c) ^ next(infinite_key_generator)))
    plaintext = "".join(chr(int(c, 16)) for c in translate_array)
    print(f"\nPlaintext is: {plaintext}\n")

if _name_ == "_main_":
    main()

This is elegant!
Not only is rc4 broken,
but I coded the above solution up from scratch,
before class, in a rush.
So, don’t rely on it to protect real secrets…

1.1.3.3 Overview of the whole process

Add key.
Generate key-stream non-linearly from array.
Generate bytes that reveal little about state of key-stream generator.
10b-SymmetricStream/f5-crop.png

RC4 is simple, and elegant,
but it is broken.
It is still too common (WEP and SSL(old)/TLS(new)!).
Over all possible RC4 keys,
the statistics for the first few bytes of output keystream are strongly non-random,
leaking information about the key.
Must discard first bits of keystream,
which helps, but not enough.

1.1.4 Salsa20/ChaCha

Google selected ChaCha20 along with Bernstein’s Poly1305 message authentication code,
as a replacement for RC4 in TLS.
Shortly after Google’s adoption for TLS,
both the ChaCha20 and Poly1305 algorithms were also used for SSH,
in a new chacha20-poly1305@openssh.com cipher in OpenSSH.

Speed
There is an AES instruction set for x86 processors.
ChaCha20 usually offers better performance than AES,
on systems where the CPU does not feature AES acceleration,
or where the software does not implement support for it.
ChaCha20 is sometimes preferred over AES,
in certain use cases involving mobile devices,
which mostly use ARM-based CPUs.

1.2 Reminder: Block Cipher Modes of Operation Mimic Streaming

1.2.1 Electronic Codebook Mode (ECB)

ECB is the simplest mode.
Plain-text is handled b bits at a time,
and each block is encrypted using the same key.
Named “Codebook” because it has a unique cipher-text value,
for each plain-text block.
Not secure for long messages,
since repeated plain-text is seen in repeated cipher-text.
To overcome security deficiencies,
you need a technique where the same plain-text block,
if repeated, produces different cipher-text blocks.
10b-SymmetricStream/pasted_image006.png