# Perpher: Fast card encryption **Abstract.** TODO **Keywords.** TODO ## 1 Introduction *A permutation cipher.* Few ciphers do not require the use of a computer. The card ciphers there are, are not as secure nor convenient as computer ciphers. Perpher bridges the gap: its design inspired from ChaCha20 gives a high security level across a very large number of messages, is resilient and has optional forward secrecy. The ciphertexts, being card decks themselves, are also less conspicuous. **NOTE: DO NOT USE YET. DESIGN STILL IN FLUX; CRYPTANALYSIS ONGOING.** ## 2 Method There are three procedures to describe the cipher. 1. **Key exchange**, in two steps: 1. Shuffle, 3. Give copies to future recipients. 2. **Encryption** of a message, which occurs block by block: 1. Hash the key, 2. Encode the block, 3. Scramble the block, 4. If the ciphertext is finished, replace the key with the block 1 hash. 3. **Decryption** of a message, also block by block: 1. Hash the key, 2. Unscramble the block, 3. Decode the block, 4. If the plaintext is finished, replace the key with the block 1 hash. ``` Key Nonce Plaintext ┌─┴──────┴─┐┌ ① Diffusion (nonce) ┌────┴───┐ │ Hash ├┼ ② Confusion (key) │ Encode │ └─────┬────┘└ ③ One-way └────┬───┘ ┌─────┴────┐ Plaintext─┤ Scramble │ block └─────┬────┘ ↓ Ciphertext block ``` ### 2.1 Key exchange We rely on shuffled card decks to encrypt information. A card deck consists of 52 cards: four colored sets of 13 numbered cards from 1 to 10, Jack, Queen, King. Two colored sets (say, black and red) therefore make up 26 items. We match each to an alphabetic letter: Black Ace is A, Black 2 is B, … Red King is Z. We use lowercase for Clubs and Hearts, uppercase for Spades and Diamonds. (Suits are ordered by the difference between outward angles and inward ones. Mnemotechnically, it is ordered by how easily it tears.) The cryptographic key is a given random permutation of a deck. A party that intends to send messages builds a key assigned to them in the following way. They thoroughly shuffle a deck (using [⌈2×log2(52)⌉ = 12 riffle shuffles][shuf], or a minute-long wash), copy the deck ordering to as many other decks as intended recipients, put in each deck a piece of paper with a random letter on it (identifying the sender as owning that key) and a single vertical bar (indicating which message number it will encrypt next). They give the extra decks to all recipients of future messages. [shuf]: http://www2.stat.duke.edu/~scs/Courses/Stat376/Papers/ConvergeRates/Shuffling/AldousDiaconisAmerMathMonthly1986.pdf The entropy of the key is log2(52!) = 225 bits. For the examples throughout, the key is abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ. In other words: 🃑🃒🃓🃔🃕🃖🃗🃘🃙🃚🃛🃝🃞 🂱🂲🂳🂴🂵🂶🂷🂸🂹🂺🂻🂽🂾 🂡🂢🂣🂤🂥🂦🂧🂨🂩🂪🂫🂭🂮 🃁🃂🃃🃄🃅🃆🃇🃈🃉🃊🃋🃍🃎 ### 2.2 Encryption Each key can encipher a virtually unlimited number of messages, each made of up to 100 blocks of 26 characters. Each message block is a deck; the block information is in its ordering. To encrypt a plaintext, first cut it into blocks of 26 letters. Each block is encrypted or decrypted independently. Thus, any message (up to 2600 characters) can be fully processed in 30 minutes with enough people handling blocks in parallel. (Rotate+deal: ~1 min, confuse: 4 min, encode: 10 min?, decode: 3:30 min, scramble: 5 min?) ### 2.3 Hash the key To encode a block, first, you copy the key to a new deck. Then, the deck is hashed in 4 rounds, each like so: 1. Take the deck with the visible card up. 2. **Diffusion**: Rotate the deck N times (ie. place the top card at the bottom). 5. **Confusion**: 1. Place the cards in thirteen rows by four, from left to right first, then top to bottom. 2. For each card in order, starting with top left, look at the previous card. 3. Find the reference position of that previous card’s value (eg. if it a Jack of Spades, it is the 11th column (Jack), third row (Spades)). The previous card of the top left one is the bottom right one; the previous card of the leftmost one on row n+1 is the rightmost on the nth row. 4. If that position is either the current card’s or the previous card’s, do nothing. (This ensures that the process is reversible.) 5. Else, swap the current card with the card there. 6. Move on to the next card. 7. Put each row on top of the row above it; and then each pile on top of the pile to its right. The rotations (N) come from the block number. The first block is 01; the second is 02; etc. For block 02, the rotations are: 2, 0, 2, 0. Then, perform the **One-way** (irreversible) step: sort by the key. 1. Place the cards in thirteen rows by four, from left to right first, then top to bottom. 2. For each card in the key deck: 1. Find the reference position of that card’s value (eg. if it a Jack of Spades, it is the 11th column (Jack), third row (Spades)). 2. In the hashed card set, find the card at that reference position. 3. Take it and place it at the bottom of the pile of cards in your hand. In our example, for block 02, the resulting deck is: Key: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ Rotate 2: cdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZab Confuse: dyhjSMpruvImBEFHYLoORTQaZUcnWgJkKXAfitPwVelzbCDqGxsN Rotate 0: dyhjSMpruvImBEFHYLoORTQaZUcnWgJkKXAfitPwVelzbCDqGxsN Confuse: jqUYBvPVfneLFxaryZNGMXzAclHSiQOJumoCDgEhkpwsTKbtdRIW Rotate 2: UYBvPVfneLFxaryZNGMXzAclHSiQOJumoCDgEhkpwsTKbtdRIWjq Confuse: BtZfOdqoSTkcAIaJYGXFmlWQvgPeUVCKEDzhisMuxjHRbpNnwryL Rotate 0: BtZfOdqoSTkcAIaJYGXFmlWQvgPeUVCKEDzhisMuxjHRbpNnwryL Confuse: sYfGECVFulAPamvkOiUMjJxNSDXdLBZqzbHrgtoTpInKwhQcyWRe One-way: sYfGECVFulAPamvkOiUMjJxNSDXdLBZqzbHrgtoTpInKwhQcyWRe ### 2.4 Encode the block Assume the plaintext block to encrypt is “thismessageistwentysixlong”. First, cut it into two chunks of 13 letters. Let’s process the first one: “thismessageis”. It is recommended that the plaintext deck be ordered in four rows (Clover / Heart / Spade / Diamond), with columns from 1 to King. For each character: 1. Convert the letter to a card, using Clovers and Hearts. For instance, T is a 7 of Hearts. 2. If the deck contains the card, place it as the next card in the plaintext block. 3. Otherwise, take the nearest smaller card, wrapping around to the highest card if there are none below; and track the number of cards off from the intended card. We get: t h i s m e r q a g d f p 1 2 1 3 3 The rest of the cards are bcjklnouvwxyz. Now, we go through the 13 cards of the plaintext block in reverse order. For each card starting with the last: 1. Let’s say that card was N cards off. (For P, it is 3 cards off.) Take the card after the Nth card in the rest of the cards. (For P, take K.) 2. This card goes at the end of the plaintext block (so, after P). At the end, we get the following plaintext block: “thismerqagdfpklcbjuonvwxyz”. Do the same for the next 13 letters with Spades and Diamonds: thismerqagdfpklcbjuonvwxyzTWENSYRIXLOMGACBDFHKJQPUVZ *Note: technically, a 52-card deck can encode log26(52!) = 47-letter messages. Our design is at roughly half the rate, but is reasonably easy to compute.* ### 2.5 Scramble the block We sort the plaintext block by the hash. It is just like the one-way step of the hash, except we use the hash as scrambler instead of the key. Here is, again, how it works. Place the plaintext block in four rows of 13 cards, from left to right, then top to bottom. The rows will represent Clubs, Hearts, Spades, Diamonds, in this order. The columns are 1 thru King. Take the first card of the scramble (the hashed deck). If it is a 4 of Spades, take the fourth card of the third row: it becomes the first card of the ciphertext block (and so, the card that will be visible at the top of the deck). Rince, repeat, with each new card placed at the bottom of the block: you now have a full ciphertext block. uVeRSEQYnfTBtpvdCaJGgLxAHNUsMWZbzhIjrolKcXkOwqDiyPFm Place a piece of paper in the block, with a message that ideally looks like a game score, where you specify: - the key identifier (which identifies you as the sender), - the message number, - the block number. ### 2.6 Send the message Once you have all the ciphertext decks for your message, prepare your key for the next message. 1. Replace your key deck with the deck that contains the hashed key you used for block 01. 2. Increment the counter on your key deck’s paper by adding a vertical bar (or crossing a set of four bars). That indicates that this key deck is now ready to encrypt the message whose number is the number of bars. Then, transmit the ciphertext decks to your recipients. ## 3 Cryptanalysis Security claims: 1. We claim an overall security level of 104 bits (from the leaklessness). 2. The hash is a PRF. 3. **Plaintext confidentiality:** Recovery of a plaintext block or the key requires resources comparable to an ideal 224-bit key cipher. 4. **Forward secrecy:** knowledge of message M’s key requires 2²²⁴ operations to decipher messages M-k for k > 0. We exclude side-channel, related-key, known-key, chosen-key attacks from those claims. We require that less than 10²⁵ blocks be encrypted with the same key. ### 3.1 Diffusion **Diffusion** is the following property: If we use a plaintext block on a different block number, then each possible permutation should appear with equal probability, without knowledge of the key. We need diffusion to ensure that the hash acts as a **Pseudo-Random Function** (PRF): in a blind test between the hash and a true random function, without knowing the key, it should be extremely unlikely to be able to tell the hash apart from the true random function by inputting block numbers (nonces) and looking at the scrambles that come out. Indeed the cornerstone of the cipher’s confidentiality is in the inability to find any pattern in each scramble and across blocks and messages. Otherwise, if one scramble is more likely for a block, then unscrambling our ciphertext with it yields a plaintext that is slightly more likely: the adversary gains information of the plaintext just from the ciphertext. Let’s call this **intra-block diffusion**. Additionally, if the use of one scramble for block B1 makes one possible scramble in block B2 more likely, then block B2’s ciphertext similarly leaks information about its plaintext, assuming the attacker guesses block B1’s plaintext. Let’s call this **inter-block diffusion**. #### 3.1.1 Discardlessness To ensure intra-block diffusion, a clearly desirable property of a cipher is that for each ciphertext, there is a key that encrypts any plaintext to it. That way, even brute-forcing the key cannot find the plaintext. Let’s call this property “discardless”; as in: we cannot discard some plaintexts based on just looking at the ciphertext and other wire-visible information such as the message and block number, even if we had infinite amounts of compute power. Consider the function `reverse_key(plaintext, ciphertext)` that outputs the set of keys that encrypt the plaintext into the ciphertext. Having a discardless cipher means that for all inputs, the output set is not empty. In Perpher, it is obvious that each plaintext block and ciphertext block have exactly one scramble. So, assuming the hash is surjective, it is discardless. (In fact, F: (key, A) → B is discardless if and only if G: A → F(key, A) is surjective for all keys.) If the hash was reversible, it would obviously be surjective. While the hash is reversible *for one known key*, it is not reversible *across all keys*. In other words, there can be impossible outputs: scrambles without preimages. (That is also a theoretical problem with AES-128: it is not discardless. While, for a given key, all 128-bit ciphertexts have a plaintext that encrypts to it (since it is a PRP); across all keys, a ciphertext may have no key that encrypts a given plaintext to it. Thus, a ciphertext may have only one plaintext that is contextually meaningful, across the set of plaintexts for which a key encrypts them to the ciphertext, therefore betraying on its own the confidentiality of its content without needing knowledge of the key nor of the plaintext; since, as we will see, only about two third of all possible plaintexts have a key that encrypt to any given ciphertext. As a consequence, for most ciphertext blocks, if you know that the plaintext can only be one of three possibilities (say, “Normandy”, “Dunkirk”, or “Norway”), you can discard one of them just by looking at the ciphertext, because there does not exist a key that encrypts it to the ciphertext.) INSERT EXAMPLE RANDOM MAPPING FROM KEY TO SCRAMBLE HERE (It is technically feasible to rely on a reversible hash and still have a secure cipher, by relying on key ambiguity described later to ensure that knowing the plaintext is insufficient to guess the scramble (and thus, the attacker cannot reverse the unguessable scramble into the key). However, the encoding process becomes more cumbersome, and the cryptanalysis described in the “key ambiguity” section up next, makes the advantages insufficient compared to a probabilistic result.) Since the hash is not surjective, and its property is apparent randomness, it maps inputs (the key and nonce) to random outputs (scrambles). *How many scrambles are impossible?* You can imagine the random hash creation process as the following. For each input: 1. Pick a random scramble among the set of O = 52! possibilities. Each output (scramble) will be picked with probability 1÷O. 2. Map the input to it. The impossible ones are those outputs that were not picked even after I iterations of this process (one for every I inputs). They need to have not been picked for the first one (which happens with probability 1 - 1÷O), nor have been picked for the second one (with same probability 1 - 1÷O), and so on. So the total probability is ΠI (1 - 1÷O) = (1 - 1÷O)^I. Interestingly, when I = O, this converges quickly to 1÷e: so about 37% of outputs are impossible, as no input map to them. Hence the AES-128 comment earlier. In our case, the input is one key out of I = 52!, and there are O = 52! possible plaintext *blocks*. But that is not all. As we will see in the “key ambiguity” section below, each plaintext of 26 letters can be encoded into 2²⁶ possible decks. The encryption process itself follows a random hash model (where the input is the plaintext and the output is the ciphertext). So the probability that not even one 26-letter plaintext belongs to the set of A = 2²⁶ plaintext blocks that map to one given ciphertext block, is Π[k=1…A] ΠI (1 - 1÷(O-k+1)) = (1-A÷O)^I = 2^-96817625, or, as common parlance would call it, “impossible”. Therefore, despite not being surjective, the cipher is such that, with high likelihood, *all ciphertext blocks can be decrypted into any possible plaintext* for at least one key. So, without the key, and assuming that the hash does behave like a PRF, it is impossible to find the plaintext of a ciphertext block with bruteforce. For future studies, we define **discardness** as the probability that an input is impossible for a given output (or equivalently, `|{(P, C): |reverse_key(P, C)| > 0}| ÷ |{(P, C)}|`, where `P` is a plaintext and `C` a ciphertext). We define **discardlessness** as -log2(discardness), to normalize it to a security level in bits. #### 3.1.2 Leaklessness However, even a discardless cipher can fail to have intra-block diffusion. For instance, take a cipher with three possible keys K1 thru K3, where K1 encrypts P1 to C, and both K2 and K3 encrypt P2 to C. If the set of all possible plaintext blocks are {P1, P2}, for all ciphertexts, there is a key that encrypts any plaintext to it. But seeing C leaks information about the plaintext: without knowing the key, assuming the key was selected randomly, C is much more likely to decrypt to P2. An interesting metric for this is the range of plaintext likelihoods for a given ciphertext, across all keys, block and message numbers. In other words, the most extreme difference between the highest probability for a plaintext, and the lowest probability for another, within a single ciphertext. Let’s call this a cipher’s **leakness**: `avg[C] ((max[P] |reverse_key(P, C)| - min[P] |reverse_key(P, C)|) ÷ Σ[P] |reverse_key(P, C)|)`. (We again also define **leaklessness** as -log2(leakness) to normalize it to a security level in bits.) It is somewhat tricky to compute exactly. However, it can be estimated based on the design assumptions. Assuming that, for a given ciphertext, keys are randomly mapped to plaintexts, then the leakness is the difference between the plaintext that has the most preimages, and the one with the least. There are N keys and P plaintexts. We are throwing each key into a random plaintext bin, and want to know the expected value of the fullest (F keys) and emptiest (E keys) bins. Then the most probable plaintext has probability F÷N, and the least probable is at E÷N, yielding a leakness of (F-E) ÷ N. The number of keys decrypting to the same plaintext follows a binomial distribution: for each plaintext, every key tries to map to it with success probability p (for instance, 1÷P if it randomly maps to one of P plaintext). So the probability that k keys decrypt the ciphertext to a given plaintext is Binomial(k; N, p) = (N choose k)×p^k×(1-p)^N-k. Since we are doing this experiment P times (one for each plaintext), the probability that at least one plaintext has k keys across the P is PK(k; N, p) = 1-(1-Binomial(k; N, p))^P. We want to find the minimum and maximum k such that PK(k) ≥ 0.5. Thus, we want the range R = argmin\[k\] (PK(k) - 0.5). The leakness is (max(R) - min(R)) ÷ P. In many cases (when max(R) is small), this can be found by computing through all values of k. For instance, for AES-128, in all likelihood, the plaintext that has the least preimages has none. The plaintext that has the most has 33 (a common inaccurate approximation is log(2¹²⁸)÷log(log(2¹²⁸)) = 20). So its leakness is 2^-122. However, when k is about 2¹⁰³, the computation of its factorial is too computationally hard. But in those cases, we can approximate the binomial distribution with a normal: PK(k; N, p) ≈ 1-(1-Normal(k; N×p, N×p×(1-p)))^P, where Normal(x; μ, σ²) = e^{-(x - μ)²÷2÷σ²} ÷ √(2×π×σ²). Solving PK(k; N, p) = ½ for k yields k = N×p ± √(-2×N×p×(1-p)×ln(√(2×π×N×p×(1-p)))×(1-½^1÷N))). Of course, only positive values are valid; so the leakness is (kmax - max(0, kmin)) ÷ P. For instance, for AES-256, we reach a leakness of 2^-59. In the context of Perpher, p, the probability of a key decrypting to a given plaintext, is 2²⁶ ÷ 52!, as there are 2²⁶ valid encodings of each plaintext. KEYS PLAINTEXT BLOCK PLAINTEXT 52! 52! 26^26 · ·┐ · ·┤ 2^26 · · ·┘ · ·┐ · ·┤ 2^26 · · ·┘ · ·┐ · ·┤ 52! - 26^26 × 2^26 · ·┘ Therefore, its leakness is 2^-104: better than AES-256, but a bit below AES-128. In other words, intra-block diffusion is good as long as the hash behaves like a PRF. And that relates to inter-block diffusion… #### 3.1.3 Inter-block diffusion To gain confidence in the randomness of the hash output, we will rely on three tools: - Probabilistic estimation of deviation from perfect diffusion, - Algebraic analysis (proving properties algebraically), - Monte-Carlo simulations (computing p-values of statistical tests). ##### 3.1.3.1 Probabilistic estimation We have a fixed key of unknown value. We encode the block number to get the hash’s input. That block’s hash input is typically a single card swap away from the previous block’s hash input. We run through the hash’s diffusion rounds, obtaining the scramble. And now, we wish to know the likelihood that any given card of this block’s scramble stayed the same as last block’s scramble. In theory, since every possible permutation should appear with equal probability on every block (regardless of how adjacent they are), a card of one block scramble should be identical as the one for any other block scramble with probability 1÷52. The way the two diffusion rounds are set up, the probability that any given card is unaffected by a given swap in the hash input is P_unaffected = ((52 cards - 2 swapped cards) ÷ 52 cards) ^ (52 cards × 2 rounds) ≅ 0.0169. Indeed, the cards are unaffected if, at each step of the algorithm, neither swapped card is called to the cursor card. Thus, the probability that the card stays the same is P_same = P_unaffected + ((1 - P_unaffected) × 1÷52). That is a deviation of |1÷52 - P_same| ≅ 0.0166 from the expected (perfect-diffusion) value. On average, between two block scrambles, 52 × P_same ≅ 1.86 cards are identical, instead of the ideal value of 1. To put that in perspective: let’s assume an attacker knows one block scramble (for instance through a known-plaintext attack). **They want to exploit that diffusion weakness** to guess another block’s scramble. They must go through every possible set of two cards in the known scramble, and brute-force all the other cards. The number of scrambles to explore is then (52 choose 2) × (52 - 2)!. That is roughly 2²²⁴. It is indeed smaller than the full permutation space of 52! ≅ 2²²⁵, but as you can imagine, it does not get our attacker very far either! ##### 3.1.3.2 Algebraic analysis TODO ### 3.2 Known-plaintext attack Some steps of the hashing (diffusion and confusion) are fully reversible. If all of them were, it would allow an attacker that knows the plaintext block and has an encrypted copy to figure out the scramble by looking at where each plaintext card landed in the encrypted block. Then, they could reverse the scramble through the hash, and get the key. The one-way step purposefully relies on the key, making this step non-reversible without knowledge of the key. *What if knowing the scramble revealed the key? Could we still be secure?* If `reverse_key(plaintext, ciphertext)` has just one item (set of cardinal 1), then only a single key can encrypt that plaintext into that ciphertext. As a result, the key can be theoretically guessed from a known-plaintext attack. If the key is thrown away, such as in a one-time pad, then having the adversary guess it is irrelevant (since they already knew the plaintext, and since the key will never be used again). But for most ciphers including this one, knowing the key usually allows you to decrypt all subsequent blocks. Let’s call **“key ambiguity”**, the smallest output size of `reverse_key()`. If it is too large (say, 2⁶⁴), even if a fast `reverse_key()` was discovered, it would be pragmatically too expensive, given two blocks where they both know the plaintext and its ciphertext, to find the common key across the two sets of 2⁶⁴ keys. A necessary property to have key ambiguity of 2^N, is to have the number of key bits minus the information content of the plaintext be larger than or equal to N. In the case of Perpher, the plaintext contains log2(26²⁶) = 122 bits, and we have a 225-bit key. So the key ambiguity can be 2¹⁰³. And indeed, note that there are multiple ways to encode the same sentence: every Club of the first 13 characters can use a Spade, and the same is true for Hearts and Diamonds. Thus, assuming an attacker knows the plaintext of a ciphertext block, there is one possible scramble, and so one possible key, for every possible encoding of the plaintext into its encoded plaintext block. There is one bit of uncertainty for each card, so sadly it only has 2²⁶ possible keys. If the attacker has a maximal practical known-plaintext break, and found a ciphertext for which they know the plaintext, they can compute `reverse_key(plaintext, ciphertext)` and instantly get that set of 2²⁶ keys for which an encoding of the plaintext gets encrypted into the ciphertext. They don’t know which key is right, so they cannot decrypt the rest. But if they had access to another ciphertext for which they knew the plaintext, *they could **store the list of possible keys** of the first block, and iterate through the list of possible keys of the second block* until they found one key in common between the two blocks. The probability of more than one key appearing for both blocks is abysmal: it is the complement of the probability that none of the keys of the first block set appear randomly in the second block set: 1 - ((N - 1) ÷ N)^A = 10^-60 with N = 52! (possible keys) and A = 2²⁶ (size of `reverse_key()` output). So the key they would find would certainly be unambiguously the key that is used for all blocks of the message. And with it, they can get the keys of all future messages as well. Of course, this would not be possible if storing the list of possible keys was physically impossible. Sadly, 2²⁶ of our keys require ⌈log2(52)⌉×2²⁶ = 50 MB, which is tractable. To reach the full 2¹⁰³ (and an untractable 10⁶ YB), you would need to encode in such a way that all permutations encode a message. Here is one small tweak to the encoding that reaches impractical territory: for every character that you encode, pick a random number N between 1 and that character’s plaintext position (N≤13). Take the Nth card lower than that card among the cards that remain available. It generates 13!² encodings, worth 2×log2(13!) = 65 bits (costing an unachievable 27 EB on its own), plus the 26 bits of the Clubs/Spades ambiguity described above, yielding 1857 YB. It would be critical to rely on a source of randomness that is independent from the random information of the key generation. Thankfully, the following scheme would be easy to perform, and computes a sequence of random numbers where the first is between 1 and N, the second is between 1 and N-1, etc.: 1. Shuffle a deck as explained in key generation. 2. Take all the Hearts in shuffle order. 3. Find the Ace. The first random number is its position (eg. if last, the number is 13). 4. Remove the Ace from the list. 5. Find the 2 of Hearts. The second random number is its position, excluding the Ace (eg. if last, the number is 12). 6. Repeat until there are no more cards. While storing all possible keys of the first block to compare with the second block’s keys is impossible, brute-forcing through the list of 2⁹¹ keys sounds on the verge of feasibility. To perform that brute-force, *one would go through each possible first-block key, use it to **decrypt the second-block ciphertext**, and compare the resulting second-block plaintext to the known second-block plaintext*. If it is a match, the key is the right one with probability 1-10^-60. Assuming decryption and plaintext comparison takes one nanosecond, it would take on average 2^91-1 ns, or 3 times the age of the universe. However, this process is parallelizable: with 100 billion computers, the key would be found in a year. That figure is on the order of magnitude of the number of CPUs in existence in 2020. As a result, unless developing a more sophisticated encoding scheme that fully exploits the 133 bits of entropy available, while still being convenient to manually encode, we chose not to rely on this level of key ambiguity as a fundamental part of our security claims. Nevertheless, if you wish to ensure that decrypting your future messages costs a terrifyingly colossal siphon of energy, in addition to a complete and trivial known-plaintext cryptographic break, in addition to your adversary guessing two plaintext decks correctly; well, you know how. Additionally, that variant would allow us to have a fully reversible hash, which would cause the cipher to have both infinite discardlessness and leaklessness. ### 3.3 Forward secrecy Since an adversary discovering the deck would lead to tremendous danger, (in fact, just the proof that a given key was used to encrypt data could cause extreme prejudice), the key used to encrypt message M is the hash of the key used to encrypt message M-1 for block 1. The irreversibility of the hash (without knowing the key) makes it implausible for the enemy to find the key for message M-1 given the key for message M. Therefore, seizing key M by force will maintain confidentiality of messages 1 thru M-1. Additionally, unless they have also intercepted message M, there is no information in key M that tells them that it is an encryption key. ### 3.4 Confusion **Confusion** is the following property: For any known key modification (eg. swapping two cards), for the same known plaintext block whose ciphertext we also know, all old ciphertext cards should appear in each new position in the deck with uniform likelihood, without knowledge of the keys. In particular, an average of one card out of 52 should remain where it is. Technically, we don’t need confusion for the cipher to be secure, assuming the key generation process is followed scrupulously. First, we can notice that, assuming the hash is a PRF, the scramble appears randomly picked across all possible permutations. Then, the plaintext’s scrambling appears like a random shuffling, so all new positions of each card is equally likely. So all we need to focus on is whether the scramble has confusion, instead of the plaintext. #### 3.4.1 Differential cryptanalysis TODO #### 3.4.2 Algebraic cryptanalysis TODO #### 3.4.3 Related-key attack Technically, if following the instructions for key generation, this attack is infeasible for an adversary, as random keys are not related. That said, even if keys were related, the confusion steps have an avalanche effect, making small changes to the key cause major differences in the final scramble. Knowing that two keys are nearly identical (such as …XYZ and …ZYX) does not let you know the relationship between the final scrambles, because even if you use stand-in variables for each card of the key, you need to know the key's exact cards to compute the confusion step. Let’s look at the absolute worst-case scenario: two keys with a single-swap change between them at the worst possible location for confusion, on the worst possible block number for diffusion. First, the worst possible key in this scenario is the ordered deck, and the worst block is block 10: Key: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ Rotate 0: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ Confuse: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ Rotate 1: bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZa Confuse: bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZa Rotate 0: bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZa Confuse: bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZa Rotate 1: cdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZab Confuse: dyhjSMpruvImBEFHYLoORTQaZUcnWgJkKXAfitPwVelzbCDqGxsN One-way: dyhjSMpruvImBEFHYLoORTQaZUcnWgJkKXAfitPwVelzbCDqGxsN You can see that there is significant bias in the first three rounds, but it disappears after the fourth. Let’s build the worst possible related key: Key: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWYXZ Rotate 0: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWYXZ Confuse: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWZXY Rotate 1: bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWZXYa Confuse: YXdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWZabc Rotate 0: YXdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWZabc Confuse: deYghajkbmnXpqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWZcfilo Rotate 1: eYghajkbmnXpqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWZcfilod Confuse: obgYKupOxMIyQEVfWJUlvzDHLPTwrkFeAjBZGXCcnRsqiNdSmaht One-way: obgYKupOxMIyQEVfWJUlvzDHLPTwrkFeAjBZGXCcnRsqiNdSmhat You can also notice that the fourth round confusion yields card positions that seem completely decorrelated from that of the other key’s fourth round. ## 4 Comparison The main comparison is with the Solitaire cipher, the only other card encryption mechanism that a state actor would likely struggle to decrypt. ### 4.1 User experience - Solitaire processes one letter per minute. With Perpher, messages above 17 letters are processed faster. - Solitaire ciphertexts are sequences of random characters. Carrying such a message, or being seen writing one, is fairly incriminating. Perpher ciphertexts look like shuffled decks, and encryption, like a game. - In Solitaire, it is easy to make a mistake. A lot of the processing involves converting cards to pseudorandom numbers in the range 0-53 (where it is easy to make an off-by-one error), and taking the Nth card in the deck (which can also be wrong). In Perpher, all operations are hard to mess up, and if you do, it is usually easy to detect. - Mistakes never recover. The communicating parties have to communicate out-of-band to notify the other that the ciphertext became unreadable, and they need to redo a key exchange every time. In Perpher, mistakes only eat the rest of the block: from 1 to 26 letters. However, if the mistake is on the first block, the following messages will indeed become unreadable and require an out-of-band key exchange. - Solitaire does not specify how to encode multiple messages. It is tempting to keep using the same key, but fully breaks all security. The proper way is to reinitiate a key exchange on every message, but this is extremely cumbersome and potentially impractical. You can resume encryption with the deck state that you got at the end of the previous message. However, the longer you use the key, the more likely it is that the adversary can break the full exchange, given the cipher’s cryptanalytical weakness. Besides, if message M is lost, the recipient may alter the deck while decoding message M+1, leading to desynchronization between them and the sender. In Perpher, encoding multiple messages is fully specified. Since it is recommended to add a piece of paper in each ciphertext deck indicating the identifier of the key and the message and block numbers, if a message is lost, it is easy to recover without a new key exchange. Finally, you run the risk of having all past communication deciphered when adversaries get a hold of the deck, since there is no forward secrecy. Perpher allows for a forward-secrecy step. - Solitaire does not specify how key exchanges happen. In particular, if two counterparties use the same key, they might send a message to each other, not knowing that the other does the same. This is critical: both messages become readable without knowing the key. Perpher specifies that each key is associated with one sender, preventing this issue. ### 4.2 Security - Solitaire is irreversible. That has the consequence that distinct starting states can converge to the same state. It removes a tiny bit of the key entropy, and cuts the average cycle. Security-wise, it means that some keys will produce a keystream that repeats faster; but it is unlikely. However, it creates uncertainty on how much data can be encrypted. Perpher, on the other hand, is fully reversible assuming you know the key, and has a fixed cycle length of 10²⁵ blocks. It can therefore encrypt about 10²⁶ characters (a hundred septillion; it takes 10¹⁰ times the age of the universe to reach the cycle if encrypting one block every 20 minutes). So each key is forever; even moreso than diamonds. - There is bias in the Solitaire keystream, which leaks information. It leaks 1 bit of information after 2000 characters. So, after 452K characters, it is theoretically possible to recover the key. It is not a strong cipher as a result. Additionally, while it did not receive much cryptanalysis as a result of its weakness, its design (similar to RC4) makes it seem likely that more analysis can weaken it further, as many events in state transitions are correlated to past events. Perpher was designed to make as many events as possible be independent. For instance, every block of 26 characters is fully independent from other blocks; and within blocks, cards are scrambled independently from each other. *For any ciphertext block, there exists a key that would decrypt it to any plaintext block.* - Solitaire is vulnerable to related-key attacks: similar keys have similar output, especially at the start. ## Annex A: Diffusion Code ```julia using Printf aes128_nk = BigInt(2)^128 # Number of possible keys aes128_npt = aes128_nk # Number of possible plaintext blocks aes128_nct = aes128_npt # Number of possible ciphertext blocks aes256_nk = BigInt(2)^256 aes256_npt = aes128_npt aes256_nct = aes128_nct perpher_nk = factorial(BigInt(52)) perpher_nptb = perpher_nk perpher_npt = BigInt(26)^26 perpher_ptb_per_pt = BigInt(2)^26 perpher_nct = perpher_nk println("# Discardlessness") println() # Probability that a plaintext cannot be decrypted to a given ciphertext, # because there does not exist a key that decrypts to it, # assuming keys are picked randomly, # and map randomly to a given plaintext with probability p. function discardness(nkeys, p) (1 - p)^nkeys end # Negative log base 2 of the discardness. function discardlessness(nkeys, p) -log2(discardness(nkeys, p)) end function disp(n) @sprintf("%.3f", n) end aes128_discardness = discardness(aes128_nk, 1/aes128_npt) aes128_discardlessness = discardlessness(aes128_nk, 1/aes128_npt) println("AES-128 discardlessness $(disp(aes128_discardlessness)) " * "(p=$(disp(aes128_discardness))).") aes256_discardness = discardness(aes256_nk, 1/aes256_npt) aes256_discardlessness = discardlessness(aes256_nk, 1/aes256_npt) println("AES-256 discardlessness $(disp(aes256_discardlessness)) " * "(p=$(disp(aes256_discardness))).") perpher_discardness = discardness(perpher_nk, perpher_ptb_per_pt/perpher_nptb) perpher_discardlessness = discardlessness(perpher_nk, perpher_ptb_per_pt/perpher_nptb) println("Perpher discardlessness $(disp(perpher_discardlessness)) " * "(p=2^-$(Int(floor(perpher_discardlessness)))).") println() println("# Leaklessness") println() # Probability of k successes after n attempts of success probability p. function pmfbinomial(n, p, k) binomial(n, k) * p^k * (1-p)^(n-k) end # Mean range of a normal distribution of variance s2, # when taking n samples. function rangenormal(s2, n) 2 * sqrt(-2*s2*log(sqrt(2*pi*s2)*(1-(1/2)^(1/n)))) end function maxnormal(m, s2, n) m + sqrt(-2*s2*log(sqrt(2*pi*s2)*(1-(1/2)^(1/n)))) end function minnormal(m, s2, n) m - sqrt(-2*s2*log(sqrt(2*pi*s2)*(1-(1/2)^(1/n)))) end # When nk keys randomly decrypt np plaintexts # into a given ciphertext with probability p, # this is the probability that at least one plaintext # has exactly k keys that decrypt to the ciphertext. function pk(nk, np, p, k) 1 - (1 - pmfbinomial(nk, p, k))^np end # Mean range of plaintext probabilities for a given ciphertext, # assuming keys are picked randomly, and map randomly # to a given plaintext with probability p. # To ease computation, kfilled is a k for which pk(k) > 0.5. function leakness(nkeys, nplaintexts, p, kfilled) # Approximate with a normal distribution if k too big. if kfilled > 1e9 && nkeys*1/nplaintexts >= 9 && nkeys*(1-1/nplaintexts) >= 9 kmax = maxnormal(nkeys*p, nkeys*p*(1-p), nplaintexts) kmin = max(0, minnormal(nkeys*p, nkeys*p*(1-p), nplaintexts)) else if pk(nkeys, nplaintexts, p, kfilled) < 0.5 throw(ArgumentError("pk(kfilled) is not above 0.5")) end kmin = kfilled while pk(nkeys, nplaintexts, p, kmin) > 0.5 kmin -= 1 end kmin += 1 kmax = kfilled while pk(nkeys, nplaintexts, p, kmax) > 0.5 kmax += 1 end kmax -= 1 end #println("min $kmin (2^$(log2(kmin)))") #println("max $kmax (2^$(log2(kmin)))") (kmax - kmin) / nplaintexts end # Negative log base 2 of the leakness. function leaklessness(nkeys, nplaintexts, p, kfilled) -log2(leakness(nkeys, nplaintexts, p, kfilled)) end aes128_leaklessness = leaklessness(aes128_nk, aes128_npt, 1/aes128_npt, 0) println("AES-128 leaklessness $(Int(floor(aes128_leaklessness))).") aes256_leaklessness = leaklessness(aes256_nk, aes256_npt, 1/aes256_npt, Inf) println("AES-256 leaklessness $(Int(floor(aes256_leaklessness))).") perpher_leaklessness = leaklessness(perpher_nk, perpher_npt, perpher_ptb_per_pt/perpher_nptb, Inf) println("Perpher leaklessness $(Int(floor(perpher_leaklessness))).") ``` ## Annex B: Considered but discarded algorithms ### B.1 Encoding #### B.1.1 Offset-Marking Encoding Assume the plaintext block to encrypt is “thismessageistwentysixlong”. First, cut it into two chunks of 13 letters. Let’s process the first one: “thismessageis”. It is recommended that the plaintext deck be ordered in four rows (Clover / Heart / Spade / Diamond), with columns from 1 to King. For each character: 1. Convert the letter to a card, using Clovers and Hearts. For instance, T is a 7 of Hearts. 2. If the deck contains the card, place it as the next card in the plaintext block. 3. Otherwise, take the nearest smaller card, wrapping around to the highest card if there are none below; and track the number of cards off from the intended card. We get: t h i s m e r q a g d f p 1 2 1 3 3 The rest of the cards are bcjklnouvwxyz. Now, we go through the 13 cards of the plaintext block in reverse order. For each card starting with the last: 1. Let’s say that card was N cards off. (For P, it is 3 cards off.) Take the card after the Nth card in the rest of the cards. (For P, take K.) 2. This card goes at the end of the plaintext block (so, after P). At the end, we get the following plaintext block: “thismerqagdfpklcbjuonvwxyz”. Do the same for the next 13 letters with Spades and Diamonds: thismerqagdfpklcbjuonvwxyzTWENSYRIXLOMGACBDFHKJQPUVZ *Note: technically, a 52-card deck can encode log26(52!) = 47-letter messages. Our design is at roughly half the rate, but is reasonably easy to compute.* Rejected because: - The encoding is slow and prone to mistakes; - You need a special storage mechanism (eg. coins) to keep track of numbers; - The deck must be cut in two, with each halves containing red+black Ace to King, which takes time to prepare; - It requires an extra scrambling step, converting the encoded block to the ciphertext, like so: Key Nonce Plaintext ┌─┴──────┴─┐┌ ① Diffusion (nonce) ┌────┴───┐ │ Hash ├┼ ② Confusion (key) │ Encode │ └─────┬────┘└ ③ One-way └────┬───┘ ┌─────┴────┐ Plaintext─┤ Scramble │ block └─────┬────┘ ↓ Ciphertext block #### B.1.2 Random-Offset-Marking Encoding Some steps of the hash (diffusion and confusion) are fully reversible. If all of them were, it would allow an attacker that knows the plaintext block and has an encrypted copy to figure out the scramble by looking at where each plaintext card landed in the encrypted block. Then, they could reverse the scramble through the hash, and get the key. The one-way step purposefully relies on the key, making this step non-reversible without knowledge of the key. *What if knowing the scramble revealed the key? Could we still be secure?* If `reverse_key(plaintext, ciphertext)` has just one item (set of cardinal 1), then only a single key can encrypt that plaintext into that ciphertext. As a result, the key can be theoretically guessed from a known-plaintext attack. If the key is thrown away, such as in a one-time pad, then having the adversary guess it is irrelevant (since they already knew the plaintext, and since the key will never be used again). But for most ciphers including this one, knowing the key usually allows you to decrypt all subsequent blocks. Let’s call **“key ambiguity”**, the smallest output size of `reverse_key()`. If it is too large (say, 2⁶⁴), even if a fast `reverse_key()` was discovered, it would be pragmatically too expensive, given two blocks where they both know the plaintext and its ciphertext, to find the common key across the two sets of 2⁶⁴ keys. A necessary property to have key ambiguity of 2^N, is to have the number of key bits minus the information content of the plaintext be larger than or equal to N. In the case of Perpher, the plaintext contains log2(26²⁶) = 122 bits, and we have a 225-bit key. So the key ambiguity can be 2¹⁰³. And indeed, note that there are multiple ways to encode the same sentence: every Club of the first 13 characters can use a Spade, and the same is true for Hearts and Diamonds. Thus, assuming an attacker knows the plaintext of a ciphertext block, there is one possible scramble, and so one possible key, for every possible encoding of the plaintext into its encoded plaintext block. There is one bit of uncertainty for each card, so sadly it only has 2²⁶ possible keys. If the attacker has a maximal practical known-plaintext break, and found a ciphertext for which they know the plaintext, they can compute `reverse_key(plaintext, ciphertext)` and instantly get that set of 2²⁶ keys for which an encoding of the plaintext gets encrypted into the ciphertext. They don’t know which key is right, so they cannot decrypt the rest. But if they had access to another ciphertext for which they knew the plaintext, *they could **store the list of possible keys** of the first block, and iterate through the list of possible keys of the second block* until they found one key in common between the two blocks. The probability of more than one key appearing for both blocks is abysmal: it is the complement of the probability that none of the keys of the first block set appear randomly in the second block set: 1 - ((N - 1) ÷ N)^A = 10^-60 with N = 52! (possible keys) and A = 2²⁶ (size of `reverse_key()` output). So the key they would find would certainly be unambiguously the key that is used for all blocks of the message. And with it, they can get the keys of all future messages as well. Of course, this would not be possible if storing the list of possible keys was physically impossible. Sadly, 2²⁶ of our keys require ⌈log2(52)⌉×2²⁶ = 50 MB, which is tractable. To reach the full 2¹⁰³ (and an untractable 10⁶ YB), you would need to encode in such a way that all permutations encode a message. Here is one small tweak to the Offset-Marking encoding that reaches impractical territory: for every character that you encode, pick a random number N between 1 and that character’s plaintext position (N≤13). Take the Nth card lower than that card among the cards that remain available. It generates 13!² encodings, worth 2×log2(13!) = 65 bits (costing an unachievable 27 EB on its own), plus the 26 bits of the Clubs/Spades ambiguity described above, yielding 1857 YB. It would be critical to rely on a source of randomness that is independent from the random information of the key generation. Thankfully, the following scheme would be easy to perform, and computes a sequence of random numbers where the first is between 1 and N, the second is between 1 and N-1, etc.: 1. Shuffle a deck as explained in key generation. 2. Take all the Hearts in shuffle order. 3. Find the Ace. The first random number is its position (eg. if last, the number is 13). 4. Remove the Ace from the list. 5. Find the 2 of Hearts. The second random number is its position, excluding the Ace (eg. if last, the number is 12). 6. Repeat until there are no more cards. While storing all possible keys of the first block to compare with the second block’s keys is impossible, brute-forcing through the list of 2⁹¹ keys sounds on the verge of feasibility. To perform that brute-force, *one would go through each possible first-block key, use it to **decrypt the second-block ciphertext**, and compare the resulting second-block plaintext to the known second-block plaintext*. If it is a match, the key is the right one with probability 1-10^-60. Assuming decryption and plaintext comparison takes one nanosecond, it would take on average 2^91-1 ns, or 3 times the age of the universe. However, this process is parallelizable: with 100 billion computers, the key would be found in a year. That figure is on the order of magnitude of the number of CPUs in existence in 2020. As a result, unless developing a more sophisticated encoding scheme that fully exploits the 133 bits of entropy available, while still being convenient to manually encode, we chose not to rely on this level of key ambiguity as a fundamental part of our security claims. Nevertheless, if you wish to ensure that decrypting your future messages costs a terrifyingly colossal siphon of energy, in addition to a complete and trivial known-plaintext cryptographic break, in addition to your adversary guessing two plaintext decks correctly; well, you know how. Additionally, that variant would allow us to have a fully reversible hash, which would cause the cipher to have both infinite discardlessness and leaklessness. ### B.2 Diffusion #### B.2.1 Rotation An early mechanism for diffusing the nonce was simply to rotate the deck N times (ie. place the top card at the bottom), at the start of each round. Then, the confusion step of the round would also cause diffusion. The rotations (N) come from the block number. The first block is 01; the second is 02; etc. For block 02, the rotations are: 2, 0, 2, 0. This was particularly used in combination with Index-Chaining Confusion. Rejected because: - For proper diffusion, a minimum of 4 rounds was expected, which is time-consuming; - The username is not included, requiring a distinct key for each sender; - A rotation requires either re-decking the cards, or shifting every card by one slot, which is slow; - The number of blocks is limited to 99. ### B.3 Confusion #### B.3.1 Dealing 1. Deal the cards into C piles face up, one card per pile, from left to right, with C the round constant. 2. Put each row on top of the row above it; and then each pile on top of the pile to its right. The round constants (C) are: 21, 5, 8, 21. (Note on constants: 21, 5, 8 are the coprimes that divide 52 farthest from an integer, with a different number of cards per pile.) Rejected because it has no diffusion yet takes time. ### B.3.2 Horizontal and vertical rotations Present the cards into a grid of 4 rows of 13 columns, face up, from left to right then top to bottom. Then for each card of the key (forward on first round, backward on second): 1. Find the card in the grid (eg. if the key card is 5 of Spades, locate the card on the 5th column, 3rd row), 2. If the key card’s position is odd (1st, 3rd, etc.), rotate the column of the card in the grid; otherwise, rotate its row. (First time, with left-to-right, top-to-bottom key order.) (The second time, we use the reversed key for diffusion. That ensures that related keys diverge: the worst key relation for the diffusion step is one where keys are identical except the end: …XYZ / …ZYX. In this case, the diffusion step causes only a 6-card difference between the keys, with the forward key. But the reversed key yields a heavy avalanche effect.) (Also, we start diffusion with vertical rotation, so that this worst-case diffusion has a higher probability of increasing differences to more cards: X and Z are both horizontal rotations, and horizontals are longer. So they are more likely to be on adjacent or identical rows.) Rejected because of slow diffusion, requiring many rounds, which is time-intensive. ### B.3.3 Index-Chaining Confusion #### B.3.3.1 Index-Chaining Confusion Description TODO: replace the diffusion step (it is already described and discarded above). To encode a block, first, you copy the key to a new deck. Then, the deck is hashed in 4 rounds, each like so: 1. Take the deck with the visible card up. 2. **Diffusion**: Rotate the deck N times (ie. place the top card at the bottom). 5. **Confusion**: 1. Place the cards in thirteen rows by four, from left to right first, then top to bottom. 2. For each card in order, starting with top left, look at the previous card. 3. Find the reference position of that previous card’s value (eg. if it a Jack of Spades, it is the 11th column (Jack), third row (Spades)). The previous card of the top left one is the bottom right one; the previous card of the leftmost one on row n+1 is the rightmost on the nth row. 4. If that position is either the current card’s or the previous card’s, do nothing. (This ensures that the process is reversible.) 5. Else, swap the current card with the card there. 6. Move on to the next card. 7. Put each row on top of the row above it; and then each pile on top of the pile to its right. The rotations (N) come from the block number. The first block is 01; the second is 02; etc. For block 02, the rotations are: 2, 0, 2, 0. Then, perform the **One-way** (irreversible) step: sort by the key. 1. Place the cards in thirteen rows by four, from left to right first, then top to bottom. 2. For each card in the key deck: 1. Find the reference position of that card’s value (eg. if it a Jack of Spades, it is the 11th column (Jack), third row (Spades)). 2. In the hashed card set, find the card at that reference position. 3. Take it and place it at the bottom of the pile of cards in your hand. In our example, for block 02, the resulting deck is: Key: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ Rotate 2: cdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZab Confuse: dyhjSMpruvImBEFHYLoORTQaZUcnWgJkKXAfitPwVelzbCDqGxsN Rotate 0: dyhjSMpruvImBEFHYLoORTQaZUcnWgJkKXAfitPwVelzbCDqGxsN Confuse: jqUYBvPVfneLFxaryZNGMXzAclHSiQOJumoCDgEhkpwsTKbtdRIW Rotate 2: UYBvPVfneLFxaryZNGMXzAclHSiQOJumoCDgEhkpwsTKbtdRIWjq Confuse: BtZfOdqoSTkcAIaJYGXFmlWQvgPeUVCKEDzhisMuxjHRbpNnwryL Rotate 0: BtZfOdqoSTkcAIaJYGXFmlWQvgPeUVCKEDzhisMuxjHRbpNnwryL Confuse: sYfGECVFulAPamvkOiUMjJxNSDXdLBZqzbHrgtoTpInKwhQcyWRe One-way: sYfGECVFulAPamvkOiUMjJxNSDXdLBZqzbHrgtoTpInKwhQcyWRe #### B.3.3.2 Index-Chaining Confusion Analysis The diffusion is much, much better than mixed horizontal and vertical rotations. However, it was rejected because the diffusion was not quite good enough to be comfortable with just two rounds (about 10 rounds would be secure). Here is the analysis of the inter-block diffusion that explains why. We have a fixed key of unknown value. We encode the block number to get the hash’s input. That block’s hash input is typically a single card swap away from the previous block’s hash input. We run through the hash’s diffusion rounds, obtaining the scramble. And now, we wish to know the likelihood that any given card of this block’s scramble stayed the same as last block’s scramble. In theory, since every possible permutation should appear with equal probability on every block (regardless of how adjacent they are), a card of one block scramble should be identical as the one for any other block scramble with probability 1÷52. The way the two diffusion rounds are set up, the probability that any given card in the hash output is unaffected by a single swap in the hash input is P_unaffected = ((52 cards - 2 swapped cards) ÷ 52 cards) ^ (52 cards × 2 rounds) ≅ 0.0169. Indeed, the cards are unaffected if, at each step of the algorithm, neither swapped card is called to the cursor card. In other words, if the swapped cards have not been used as index to select a card to move to the cursor card. Thus, the probability that the card stays the same is P_same = P_unaffected + ((1 - P_unaffected) × 1÷52): either the card was unaffected, or it was affected and randomly ended up in the same place anyway. That is a deviation of |1÷52 - P_same| ≅ 0.0166 from the expected (perfect-diffusion) value. On average, between two block scrambles, 52 × P_same ≅ 1.86 cards are identical, instead of the ideal value of 1. But that average hides a sinister truth: when the swap does not affect the deck, all the cards are identical except for the two. To put that in perspective: let’s assume an attacker knows 60 plaintext blocks, and are either given their respective ciphertext blocks, or some randomly shuffled set of decks. **They must guess which it is by exploiting that diffusion weakness**. On average, 0.0169 × 60 = 1.014 blocks have not been affected by the card swap that encodes the block number. They will notice that a majority of the cards are unchanged compared to the previous block, and thus know that it is not a random shuffle. ### B.3.4 Wandering-Origin Confusion The deck is laid out in 4 rows of 13 cards. First, the Origin position is set to the top left card’s face value. For instance, 5 of Hearts would give the second row, 5th column. The Origin can be tracked with a coin. For each card from top to bottom, left to right: 1. Take that cursor card. 2. Find the card position located by applying the cursor card’s face value as a vector to the Origin. For instance, Jack of Diamonds on an origin located at 5 of Hearts (row 2, column 5) is 9 columns to the right, 3 rows below. With wrap-around, we land at row 1, column 2. 3. Swap the cursor card with the target card at that position. 4. Move the Origin to the position located by applying the target card’s face value as a vector to the Origin. This algorithm achieves perfect diffusion. Indeed, we can easily prove that, from the top left card, to the cursor card, each card has been used as index for a vector application. As a result, they have each caused all subsequent card swaps to target cards that would not be the same if their face value was different. Thus, any card swap affecting one of those indexed cards, would affect the values of all subsequent cards being swapped. At the end of one round, the top left card is affected by itself; the second card is affected by the first two cards; the third card is affected the first three cards… And the last card is affected by all cards. Therefore, after two rounds, all cards are affected by all cards. There is a bit of subtlety in the design. For instance, steps 2 and 4 must use the same Origin (instead of having step 4 use the target card position as origin), because otherwise, the target card and the next cursor card can be swapped without changing the output. The reason is that vector addition is commutative, so each vector application must be followed by a permanent change. The main issues are: - This procedure is time-consuming (~10 min per round); - It does not provide irreversibility, requiring an extra step. #### B.3.4.1 Proof of inter-block uniformity **Uniformity** means that every face value appears with equal probability at any place in the scramble, from block to block, for any given key. We prove it by induction over each step of the hash, cardwise. First, let’s look at the iteration that causes the swap with the top left card as cursor. Given that the key is random, the face value of the first card is random. That sets the first Origin location to a random card. Applying the same vector to the Origin similarly yields a random card of the deck. The cursor card is swapped with that card; thus it remains at its location in one case out of 52: when the target card is the cursor card. We have the expected probability for uniformity: all cards have an equal probability of 1÷52 of landing on the cursor card. Now, let’s go over the induction proof. Assume that, after all previous iterations, each of the cards up to the current cursor card excluded, are such that each face value has probability 1÷52 of being there. After the current iteration, is that true of all cards up to the cursor included? #### B.3.4.2 Proof of diffusion **Diffusion** means that the probability that one bit of output doesn’t change, given that one bit of input does, should be the same as random output. In our case, it implies that any swap of two cards in the input of the hash, should maintain the face value of any given scramble card position with probability 1÷52. Since the input block encodes both the key and the block nonce, it ensures that each block seems indistinguishable from random relative to each other, and that the key is sufficiently confused (in Shannon’s definition: that each ciphertext bit depends on all key bits). The metric we use to compute diffusion is min_ik -log2 |1÷52 - p_ik|, where p_ik is the probability that the output card at position i changes face value if the swap k is made on the input. Our goal is to prove that it is infinite. #### B.3.4.3 Proof of unpredictability (PRF)