Computer Science notes ⇒ Cryptography, Attacks and Countermeasures

Two major approaches to cryptography are the private, or symmetric, key cryptography approach and the public key approach. In the private key, the encrypting and decrypting keys K and K^-1 are the same (are one is easily derivable from the other). With public key cryptography, the two keys are different, and it is very difficult (without special knowledge) to derive one key from the other.

Public key cryptography has arisen in the last 30 years, and has been invented more than once: first secretly by GCHQ's Cox and Ellis, and then publicly by Diffie and Hellman. Private key cryptography has a much longer history.

With massive computational power become available, such as grid computing, or using cheap specialised hardware such as FPGAs, brute force attacks are possible.

Another general idea of cryptanalysis is to detect and exploit structure in the relationship between plaintext inputs, the key used and the ciphertext outputs. This can be used to derive keys, but weaker breaks are important - being able to tell what type of cryptographic system a stream is encrypted with gives us a foot in the door, as you should not be able to tell random streams apart. This attack detects leaking strcture.

The general idea of cryptographic systems it to make the plaintext to ciphertext mapping as random looking as we can. Sometimes, using an attack by approximation, we can detect a structural relationship in the operation of an algorithm, which exists with some small bias (i.e., an apparent deviation from random-ness).

Some schemes are based on the assumed computational difficulty of solving instances of particular combinatorial problems (e.g., knapsacks, perceptron problems, syndrome decoding). Solving such problems may not be as hard as we think. As NP-complete is about the worst case, cryptography cares more about the average case.

Cryptography is based on the idea that factorisation really is hard.

We can also attack the implementation. Mathematical functions simply map inputs to outputs and exist in some conceptual space, but when we have to implement a function, the computation consumes resources: time and power.

Encrypting data with different keys may take different times. The key and the data affects the time taken to encrypt or decrypt, which gives a leakage of information about the key. Even monitoring power consumption may reveal which instructions are being executed.

The Caesar cipher works by shifting letters of the alphabet some uniform amount, e.g., if it was a Caesar cipher of 3, A becomes X, B becomes Y, etc, so BAD becomes YXA. This is hardly the most difficult cipher to break. These classical ciphers operate on characters or blocks of characters (modern implementations operate on bits, or blocks of bits).

This early cipher was used by Julius Caesar, and works on the normal ordered alphabet, and shifts letters by some number - this number is the key k. If we map the alphabet onto the range of integers 0-25, then the Caeser cipher encrypts the characters corresponding to x as the character corresponding to (x + k) mod 26.

As there are only 26 keys, it is simple to brute force this cipher. Occasionally, we may get more than one possible decryption, but this is only likely if there is a very small amount of ciphertext.

A simple substitution cipher is simply an injective mapping: f : Π → Π, where Π is the alphabet.

All instances of a word are enciphered in exactly the same way. The appearance of these repeated subsequences in the ciphertext may allow the cryptanalyst to guess the plaintext mapping for that subsequence (using the context of the message to help).

If you actually know some of the plaintext, than these sort of ciphers are fairly trivial to break, you don't need much in the way of inspired guessing.

This problem arises because identical plaintexts are encrypted to identical ciphertexts.

Another possible attack arises due to the nature of natural language - in particular, the frequency of character occurence in text is not uniform. Some characters are more common than others, e.g., "e" in English text, as well as pairs (bigraphs), "th", etc.

Unfortunately for simple substitution ciphers, this structure in the plaintext is simply transformed to corresponding structures in the ciphertext. If the most common ciphertext character is "r", then there is a good change that it will be the encryption of "e" (or one of the other highly frequent characters).

One thing to be aware of is that the frequency tables are compiled using a great deal of text, any particular (especially true if the ciphertext is shorter) text will have frequencies that differ from the reference corpus. Thus, mapping the most frequent ciphertext character to the letter "e" may not be the right thing to do, but mapping it to one of the most popular characters probably is.

One way to address this problem is to allow each character to be encrypted in multiple ways, or use multiple ciphers.

One solution homophonic substitution, that is. to have a separate (larger) ciphertext alphabet and allow each plaintext character to map to a number of ciphertext characters. The number of ciphertext characters corresponding to a plaintext character is directly proportional to the frequency of occurrence of the plaintext character.

e.g., I has a frequency of 7 compared to V's 1, so I would map to 7 characters and V would map to 1. In this way, the ciphertext unigram statistics become even.

Vigenere made an extremely important advance in classical ciphers. He chose to use different ciphers to encrypt consecutive characters. A plaintext is put under a repeated keyword, with the character for that particular point to index the actual cipher used.

This appears to solve the problem - the statistics are flattended, but if we were to measure the frequencies of subsequences of the ciphertext (e.g., for key length 4: subsequences, 1, 5, 9, 13, etc, and 2, 6, 10, 14, etc...), we might expect these frequencies to be approximately those of the natural language text as usual.

In order to figure out the size of the keyword, or the period of the cipher, we look for n-grams occurring frequently in the ciphertext (e.g., frequent bigrams, trigrams - the bigger the better). The chances are that they correspond to idential plaintext enciphered with the same component ciphers (positions at some multiple of the period).

Once we have this period, we can apply earlier frequency analysis to each component cipher. Bi-graph frequencies can help too.

Substitution ciphers have a nice property - keys that are nearly correct give rise to plaintexts that are nearly correct. This allows from some interesting searches to be carried out. If you can measure how "good" your current key guess is, you can seek over the keyspace in order to maximuse this measure of goodness.

Of course, we can not know how good our current key guess is without knowing the actual plaintext, but we can use frequency statistics under decryption to key K to give us a strong hint.

A typical search starts with a key K (a substitution mapping), which makes repeated moves swapping the mapping of two characters, with the general aim of minimising the cost function derived from the frequency analysis. This is non-linear, and you run the risk of getting stuck in local optima.

Transposition ciphers "shuffle" the text in some way - a simple transposition cipher f might permute consecutive blocks of characters, e.g., for a reversal permutation: f = (4, 3, 2, 1), encrypt_f(JOHNHITSJOHN) = NHOJSTIHNHOJ.

To create a transposition cipher, we chose a period L, and a permutation of the numbers 1..L. The plaintext is then written out in rows of length L, and the columns are labelled according to the permutation chosen (e.g., 6 3 1 2 5 4), and then the columns reorganised in ascending order according to their label.

Unigram statistics can be used to tell us this is a transposition cipher, as the statistics will be very similar to that of plaintext.

Bi-gram statistics are rather important, and we can use similar sort of tricks as earlier to determine the period. If you guess the period wrongly, and try to find a permutation, you will be hard pressed to find pairs of columns in the decryption which have appropriate bigram statistics when considered consecutively. If you guess the period correctly, then it is possible to find pairs of columns with good bi-gram frequency statistics.

We can do searches over the permutation to find the approximate order (using the bigram cost function identified earlier).

We can also use the dictionary (or a subset of it, most people only use a limited amount of it in daily conversation) to scan the obtained plaintext to see whether it contains known words. If it does, this suggests that corresponding parts of the key are correct - this has been greatly facilitated by computers.

At each iteration, there is a right shift, a bit fall off the end and the leftmost bit is set according to the linear feedback function.

We want the stream to be random looking. One feature should be that the stream should not repeat itself too quickly. As this is, in effect, a finite state machine, it will repeat itself eventually, and the maximal period for an n-bit register is 2ⁿ-1 (it can not be 2ⁿ as if the register was all 0, it would get stuck).

The tap sequence defines the linear feedback function, and is often regarded as a finite field polynomial. You have to choose the tap sequence very carefully. Some choices provide a maximal length period, and these are primitive polynomials.

The above polynomial has a maximum period, and it is common to denote this as C(D) = 1 + D + D⁴. A similar polynomial, C(D) = 1 + D + D³ does not give a maximal period sequence.

This kind of implementation is not good for pseudo-random number generation. If we had a 64-bit register, then once we know a very small amount of plaintext (e.g., 32 consecutive bits), then you can calculate the corresponding key stream and so know the rightmost 32 bits of the register. The remaining 2³² bits can be brute forced quite easily, and when you get the right one, the whole key stream should be generated.

This is far too easy to break, but LFSRs are very easy to implement, and are fast. To fix matters, we can use a less primitive way of extracting the key stream, or even combining several streams to achieve better security.

A very simple model would involve using some function, f to operate on some subset of the LFSR register components.

A boolean function on n-inputs can be represented in the minimal sum (XOR, or +) of products (AND .) form:

f(x₁, ..., x_n) = a₀ + a₁.x₁ + ... + a_n.x_n + a_1,2.x₁.x₂ + ... + a_{n - 1, n}.x_{n - 1}.x_n + ... + a_{1, 2, ..., n}.x₁.x₂...x_n.

This is called the algebraic normal form of the function.

The algebraic degree of the function is the size of the largest subset of inputs (i.e., the number of x_j in it) associated with a non-zero co-efficient.

e.g., 1 is a constant function (as is 0). x₁ + x₃ + x₅ is a linear function, x₁.x₃ + x₅ is a quadratic function, etc.

A very simple model with a linear f would be pretty awful. If we knew a sequence of keystream bits, then essentially every key stream output can be expressed of a linear function of elements of the initial state. We can derice a number of these equations and then solve them by standard linear algebra techniques.

A non-linear f is slightly better, but it is still possible to attack such systems if f is approximated by a linear function.

Please see slide 5
for more detail.

Given f(x₁, ..., x_n), it is fairly straightforward to derive the ANF. If we consider the general form, the constant term a₀ is it is f(0, ..., 0) (the 0's cancel out any other term).

The classical model involves a series of n-bit registers with some function f, where the initial register values form the key.

The LFSRs need not all be the same length, and the LFSRs will give a vector input which has a period that is the product of the least common multiple of the periods of each of the LFSRs.

An awful choice for f would be f(x_1j, x_2j) = x_1j. If the LFSRs were 32-bits long, this would disregard 32 of those bits, leading to our key size to be effectively 32 bits.

XOR would use all 64 bits, but would still not be a good choice. If the stream bit is 0, then there are only 2 possible pairs - similarly if the stream value is 1. This again reduces our key size to 32 bits.

These examples are extreme, but beware of linearity, even a hint of it can cause weaknesses.

A Geffe generator works by using a nx1 multiplexor, with n + 1 LFSRs, with one being used for select. For a 2x1 multiplexor, this gives us the equation: Z = (a & b) + (not(a) & c).

If we put this into a truth table, we see that the output Z agrees with b 75% of the time, and also agrees with c 75% of the time.

If we consider each possible initial state s of the second register and then determine the stream produced from this initial state, we can check the degree of agreement of this stream with the actual key stream. If state s is correct, we will get roughly the right amount of agreement. If it is incorrect, the agreement will be roughly random.

We can target the third register in exactly the same way, and then can derive the first register (the selector) very easily by trying every possible state. The correct one would allow us to simulate the whole sequence. There are other ways too.

These divide and conquer attacks were suggested by Siegenthaler as a means of exploiting approximate linear relationships between function inputs and its ouput. This led to new criteria being developed as countermeasures to these correlation attacks.

If we have two functions f(x₁, x₂) and g(x₁, x₂), we say that f(x₁, x₂) is approximated by g(x₁, x₂) if the percentage of pairs (x₁, x₂) which given the same values for f and g differs from 50%.

If they agree precisely half the time, we say that they are uncorrelated. If the agreement is less than 50%, we can do g(x₁, x₂) + true to find a function with positive agreement.

We can consider similar ideas for n-input functions: f(x₁, x₂, ..., x_n) and f(x₁, x₂, ..., x_n). The degree of approximation with linear functions may be slight, and the smaller the degree of approximation, the more data you need to have to break the system.

The idea of multiple LFSRs is that the size of the keyspace should be the product of the keyspace sizes for each register. Divide and conquer reduces this to a sum of key sizes, and you can attack each in turn. When you crack one LFSR, the complexity of the remaining task is reduced (e.g., f(x₁, x₂) = x₁.x₂ + x₁ - once you know what x₁ is, then whenever you know x₁ = 1, you know what x₂ is).

In a similar vein, if we suppose there is a small exploitable correlation with input x₁ and there is a small correlation with x₁ + x₂. If LFSR can be broken to reveal x₁, then we now have a straightforward correlation with x₂ with which to exploit.

Boolean functions are, unsurprisingly, those of the type: f : {0,1}ⁿ → {0,1}. We can also consider a polar representation (f^(x)), where f^(x) = (-1)^f(x).

Boolean functions can be regarded as vectors in R²ⁿ with elements 1 or -1 (derived from our polar form). Any vector space has a basis set of vectors, and given any vector v, it can always be expressed uniquely as a weighted sum of the vectors in the basis set.

If the basis vectors are orthogonal and each have a normal length (1), we can say they form an orthonormal basis. We can express any vector in terms of its projections onto each of the basis vectors.

Given a basis, you can always turn it into an orthonormal basis using the Gram-Schmidt procedure. Given an orthogonal basis, you can always create an orthonormal one by dividing each vector by its norm.

n-dimensional vectors can be normalised in the same way, the norm is the square root of the sum of the squres of its elements.

Read the slides.

If we recall that for any ω in 0..(2ⁿ - 1), we can define a linear function for all x in 0..(2ⁿ - 1) by L_ω(x) = ω₁x₁ XOR ... XOR ω_nx_n, where ω and x are simply sequences of bits.

We will use natural decimal indexing where convenient (e.g., ω = 129 = 10000001).

The polar form of a linear function is a vector of 1 and -1 elements defined by L^_ω(x) = (-1)^{omega;₁x₁ XOR ... XOR ω_nx_n} = ∏ⁿ_{j = 1}(-1)^ω_jx_j.

One criterion that we may desire for combining function is balance (that is, there are an equal number of 0s and 1s in the truth table form, and there are an equal number of 1s and -1s in the polar form), so the polar form has elements that sum to 0, or, if you take the dot product of the polar form of a function with the constant function comprising all 1s, the result is 0.

Each linear function has an equal number of 1s and -1s (and so is a balanced function).

Dissimilar linear functions are orthogonal. If we consider the dot product of any two columns of the 8×8 matrix given in the slides, the result is 0.

The linear functions are vectors of 2ⁿ elements each of which is 1 or -1, the norm is therefore 2^{n / 2}, and thus we can form an orthonormal base set.

Since a function f is just a vector, and we have an orthonormal basis, we can represent it as the sum of projections onto the elements of that basis using the Walsh Hadamard function.

Various desirable properties of functions are expressed in terms of the Walsh Hadamard function, e.g., balance means that the projection onto the constant function should be 0.

We saw that functions that looked like linear functions too much were a problem, but a measure of agreement is fairly easily calculable (Hamming distance with linear function in usual bit form, in polar form, we simply take the dot product of the linear function).

A function f that has minimal useful agreement (i.e., 50% agreement) with L_ω has Hamming distance 2^{n / 2} with it (or, in polar terms, half the elements agree and half disagree). If all the elements disagree (i.e., f = not L_ω), we can form another function that agrees with L_ω entirely by negating f (i.e., f + 1).

If correlation with linear functions is a bad idea, let's have all such correlations equal to 0 (i.e., choose f such that the projections onto all linear functions are 0). This is not possible, however. Because we have a basis of linear functions, if a vector has a null projection onto all of them, it is the zero-vector.

A Boolean function is not a zero-vector, it must have projections onto some of the linear function. But some projections are more harmful than others, from the point of view of the correlation attacks.

These correlations with single inputs are particularly dangerous, with the danger decreasing proportional to the number of inputs.

Correlations with single inputs correspond to projections onto the L_ω where the ω has only a single bit set. Similarly, correlations with linear functions on two inputs correspond to the projections onto the linear functions L_ω where the ω has only two bits set.

If a function has a null projection onto all linear L_ω functions with 1, 2, ..., k bits set in ω (i.e., it is uncorrelated with any subset of k or fewer inputs), the function is said to be correlation immune of order k. If it is also balanced, then we say it is resilient.

For a variety of reasons (there are other attacks that exploit linearity), we would like to keep the degree of agreement with any linear function as low as possible. If we can not have all that we want (all projections 0), we can try to keep the worst agreement to a minimum.

This leads to the definition of the non-linearity of a function. We want to keep the Hamming distance to any linear function (or its negation) as close to 2^{n / 2} as possible. Or, keep the maximum absolute value of any projection on a linear function to a minimum, that is, keep max_ω|F^(ω)| as low as possible.

Non-linearity is defined by: N_f = 0.5(2ⁿ - max_ω|F^(ω)|). It seems to minimise the worst absolute value of the projection onto any linear function, but what is the maximum value we can get for non-linearity?

We can project these vectors onto a basis of 2ⁿ orthogonal (Boolean function) vectors L₀, ..., L_{2ⁿ - 1}, where L_ω(x) = ω₁x₁ XOR ... XOR ω_nx_x.

Bent functions were first researched by Rothuas, and maximise non-linearity, and are function based on even number of variables. Bent functions have projection magnitudes of the same size, but with different signs. This includes projection onto the constant function, not a balanced function, therefore if you want maximum non-linearity, you cannot have balance.

Additionally, non-linearity and correlation immunity are in conflict, as it requires an increase in the magnitude of the vectors.

All other things being equal, we would prefer more complex functions to simpler ones. One aspect that is of interest is the algebraic degree of the function, which we would like to be as high as possible.

This causes a conflict with correlation immunity. Sigenthaler has shown that for a function f on n variables with correlation immunity of order m and algebraic degree d, we must have m + d ≤ n, and for balanced functions, we must have m + d ≤ n - 1.

There is another structure that can be exploited. It is a form of correlation between outputs corresponding to inputs that are related in a straightforward way. This is autocorrelation.

The Data Encryption Standard (DES) has a very controversial history. It was developed on behalf of the US government based on previous work done by IBM. It was first issued in 1976 as FIPS 46, and has a 56-bit key (the key is actually 64-bits long, but it has check bits).

DES has generally been the first chose in commerce (e.g., banking).

DES has a public design which has been subject to attack by virtually all of the world's leading cryptanalysts. The publication of the standard has had the greatest affect on the development of modern day public cryptology than any other single development.

The 56-bit key length is controversial. It was originally 128, but was reduced by the NSA. The NSA also changed the configuration of the S-boxes. Many people are suspicious of the NSA's motives, and the design criteria for the algorithm was never revealed. Some suspect that there is a trapdoor in the algorithm.

Each round is indexed by a 48-bit subkey K₁ derived from the full key. 16 rounds in total are applied.

The initial permutation simply permutes the 64 bits of input according to a specific pattern. It has no security significance.

Each round takes the form given below, operating on the left and right 32-bit words. The XOR is a bitwise XOR of the 32-bit words.

To decrypt, the same algorithm is applied with the subkeys in reverse order. The final round is followed by a swap.

Each round includes a swap, so applying a swap immediately afterwards simply undoes it. It is clear that the method simply decrypts as expected. Induction can be used to show that the property holds for an arbitrary number of rounds.

The S-boxes take 6-bit inputs and give 4-bit outputs.

All S-boxes are different and are represented using tables. For an input b, we interpret b₁b₆ as an integer in the range 0..3 as the row to use, and b₂b₃b₄b₅ as an integer in the range 0..15 indexing the column to use. Each entry in the table is represented by a decimal and indexed as 4-bit binary.

For the expansion and P-permutation stages, each outer bit in a block of four influences the row used to do substitution in the nearest neighbouring block of four. P-permutation is straightforward permutation.

The 56-bit key is split into two 28-bit halves, and each half is subject to a cyclic shift of 1 or 2 bits in each round. After these shifts, a sub-key is extracted from the resulting halves. This is repeated for each round.

The theoretically promising cryptanalytical method of differential cryptanalysis emerged in the laste 80s, but DES was surprisingly resilient to this attack vector. Coppersmith (1994) revealed some of the design criteria, and the reason for DES's resistence to differential cryptanalysis - that it was specifically designed to be so.

This means that IBM and the NSA knew about this method of attack over 16 years before it was discovered and published by leading cryptograhpic academics.

A later technique known as linear cryptanalysis exists which DES is vulnerable to, which reduces the number of operations for a brute-force crack from 2⁵⁵ to 2⁴³.

Diffie & Hellman proposed a key search machine that would be able to break DES at a cost of $20M (1977), and a detailed hardware design for a key search machine was published by Wiener in 1993. The EFF in 1998 successfully cracked DES in 3 days using purpose built hardware that took less than 1 year to build at a cost of less than $250,000.

FPGAs now exist that can crack DES in 2 hours.

An interational competition was held to find a replacement for DES, which resulted in Rijndael's Advanced Encryption Standard being chosen. The competition was very public, as was the evaluation of it.

AES uses quite simple operations and appears to give good security as well as being very efficient. Many are now attacking the standard.

Electronic code book is the most primitive means of using block algorithms for message or data encryption. Successive blocks of plaintext are encrypted directly using the block cipher (the plaintext block is the input and the encrypted result is the ciphertext sent).

This leads to a problem where message blocks that contain the same values are always mapped to the same ciphertext values. Code books can be built up, where once we know that a particular block contains a certain enciphered form, we can recognise it if it occurs again. This kind of attack also occurred using classical ciphers.

More problematic is that the codebook can be used to forge messages pretending to belong to one of the legitimate communicants, as elements of messages can be replaced very easily.

This kind of encryption may be more suited to randomly accessed data (e.g., databases). ECB use is rare, and other modes are more common.

There is clearly a need to mask the occurrence of identical plaintext blocks in messages. It is possibly to do this by allowing the data sent so far to affect the subsequent ciphertext blocks.

Cipher Block Chaining (CBC) is a widely used means of doing this. It XORs the plaintext block with the previously produced ciphertext block and then encrypts the result.

To recover the plaintext in such a system, you must first decrypt the appropriate ciphertext block, and then XOR it with the preceeding ciphertext block to get the plaintext.

Initial blocks are crucially important. If the same initial block is used for different messages, then it will be clear when messages have the same initial sequences. The usual solution to this is to vary the initial block in some way. There is a general notion that initial blocks should not be repeated between messages. This cna be achieved by randomess (this is generally the best), but some texts advocate simply incrementing.

The matter of initial blocks is subtle, and many texts can be downright dangerous in their advice.

If we want to transmit encrypted data a character at a time (e.g., from a terminal to a host), cipher feedback mode is often useful as it can enxrypt plaintext of a size less than the block size.

Typically 8-bit sub-blocks are used, but even 1-bit sub-blocks are possible.

Using the definitions of algorithm strength (non-linearity and auto-correlation), we can use search to find the best ones satisfying these criteria.

The definitions of these (given in the relevant sections above) can easily be evaluated given a function ƒ. They can therefore be used as the expressions to be optimised (and traditionally they are).

Hill Climbing

Simulated Annealing

However, there are more advanced versions of the cost function we can consider than the simple non-linearity/autocorrelation ones above.

Parseval's theorem states ∑^{2n - 1}_{ω = 0} F^(ω)² = 2²ⁿ, so loosely we can push down on F(ω)² for some particular ω and it appears elsewhere. This suggests that arranging for uniform values of F(ω)² will lead to good non-linearity - bent functions achieve this but we shall be concerned with balanced functions. This is the motivation for a new cost function:

cost(f) = ∑^2n-1_ω=0 | | F^_ƒ(ω) | - X | ^R.

This considers the cost not for one particular input but for all inputs, to ensure that the function is optimised for all cases, not specific ones.

Moves in our search should also preserve balance. Balance is the number of 0s and 1s output. In order to preserve balance, we start with a balanced (but otherwise random) solution, and then our move strategy preserves it. This is done by defining the neighbourhood of a particular function as the set of functions obtained by exchanging two dissimilar values. We should also note that neighbouring functions have close non-linearity and autocorrelation, providing some degree of continuity.

Minimising the cost function family by itself doesn't actually give good results, but is good in getting in the right area. Our actual method is:

• Using simulated annealing to minimise the cost function given (for given parameter values of X and R), with the resulting function being ƒ_sa;
• Hill-climb with respect to non-linearity (using the non-linearity targeted techinque), or;
• Hill-climb with respect to autocorrelation (the autocorrelation targeted technique).

In 1995, Zheng and Zhang introduced two global avalanche criteria (autocorrelation and sum-of-squares), so autocorrelation bounds are receiving more attention. The sum-of-squares conjecture seemed to give poor results.

Another approach is correlation immunity, which seeks to punish a lack of correlation immunity (the first part of the formula) and low non-linearity. The cost function here is:

cost(ƒ) = ∑_|ω|≤m | F^_ƒ(ω) |^R + A × max_ω | F^_ƒ(ω) |

We can do a linear transformation for correlation immunity. If we let WZ_ƒ be the set of Walsh zeros of the function ƒ: WZ_ƒ = { ω : F^_ƒ(ω) = 0 } (that is, the inputs where the Walsh Hadamards are 0).

If Rank(WZ_ƒ = n, then we can form the matrix B_ƒ whose rows are the linearly independent vectors from the Walsh zeros. We can now let C_ƒ = B_ƒ^-1 and let ƒ′(x) = ƒ(C_ƒ x).

This resulting function ƒ′ has the same nonlinearity and algebraic degree and is also CI(1) - correlation immune. This can be applied to the basic functions generated earlier.

We can also use these techniques to plant, and detect, trapdoors left in cryptographic functions.

If we are planting a trapdoor, we first want to find a function with high non-linearity and low autocorrelation (that is, belongs in our set of Public Goodness functions - P), but also has our trapdoor function (functions in the subset of the design space - T), so we need our function to be in the set P ∩ T.

If we suppose we have an effective optimisation based approach to getting functions with this public property (P) as discussed above, we can let our cost function be cost = honest(ƒ). If we similarly had an effective optimisation technique to find functions with our trapdoor property T, we could let our cost function = trapdoor(ƒ).

We can combine the two to find a function we actually want to use: sneakyCost(ƒ) = (1 - λ) × honest(ƒ) + λ × trapdoor(ƒ), where λ is the malice factor (λ = 0 is trult honest and λ = 1 is wicked).

We want to be able to tell whether an unknown trapdoor has been inserted. Experiments have used a randomly generated vector as a trapdoor, and closeness to this vector represents a good trapdoor bias. We can investigate what happens when different malice factors are used if high non-linearity and low autocorrelation are our goodness measures.

Of all our publicly good solutions, there are two distinct subsets, those found with a honest cost function, and then with a high trapdoor bias found by combining trapdoor functions.

There appears to be nothing to distinguish the sets of solutions obtained, unless you know what form the trapdoor takes, however... If we represent two groups of functions as vectors and calculate the mean vectors, projecting one onto teh other and calculating the residual r. This represents the λ value.

The best-known public key encryption algorithm was published in 1978 by Rivest, Shamir and Adleman, it is universally called RSA. It is based on the difficulty of factoring a number into its two constituent primes.

In practice, the prime factors of interest will be several hundred bits long.

First, we pick two large primes p and q, and calculate n = p × q. e is found relatively prime to (p - 1)(q - 1), i.e., no factor in common other than 1. We then find a d such that e × d = 1 mod (p - 1)(q - 1), e.g., using Euclid's algorithm.

e is the public key and d the private key. e and n are released to the public.

Encryption and decryption are actually the same operation: C = M^e mod n and M = C^d mod n.

RSA set up a very successful company and became the world's most celebrated algorithm. However, it turns out the ideas were developed at GCHQ in the late 60s and early 70s by Ellis and Cox. Additionally, in 1974 Williamson developed an algorithm that would later be known as the Diffie-Helman algorithm.

A hash function takes some message M of an arbitrary length and produces a reduced form, or digest, H(M) of a fixed length.

Hash functions have several desirable properties:

• Given M it is easy to compute H(M);
• Given a hash value h it is hard to compute M such that h = H(M) (i.e., hash functions are one-way);
• Given M, it is hard to find another message M′ such that H(M) = H(M′) (hash functions should be resistant to collisions).

In an open use of a hash function, sender A sends a message M together with hash value: (M, H(M)). The receiver then calculated H(M) from M and checks that the result agrees with the encrypted hash value. If so, then B may assume that the message has not been altered since it was sent, but he can not prove it was sent by A.

However, we can use hash functions in an authenticated way. If we assume A and B share a key K, then sender A sends a message M together with the encrypted hash value: (M, E(K, H(M))). The receiver then calculates H(M) and encrypts it with the key K, checking whether the result agrees with the encrypted hash value received. If it does, then B can assume that the message has not been altered since it was sent, and that the message was sent by A.

Encrypting just the hash value is faster than encrypting the whole message.

This of course assumes that A and B trust other: A can not prove that B created a message or vice-versa (either could have just made it up themselves). But with variants of public key cryptography (e.g., RSA), we can get the sender to encrypt the hash using his or her private key - we say the hash is signed.

If our hashing algorithm was not resistant to collisions, then we could monitor the network for a message (M, E(K, H(M))) and record it, and then find a message such that H(M′) = H(M), and then forge a message (M′, E(K, H(M))).

Pollard's Rho Method

Fermat Factorisation

Probably the most important factor base methods to emerge in recent years have been variants of the quadratic sieve developed by Pommerance. This has been the best performer for n with no factor or order of magnitude significantly less than √n. The most recent is the number field sieve.

The best general purpose algorithm typically had a complexity of Ο(e^{(1 + ε)√log n log log n)}), however number field sieve has the complexity exp(Ο((log n)^1/3 (log log n)^2/3)).

The knapsack scheme was at the heart of the first published public key scheme, but is fraught with danger.

Variants on the knapsack problem have proven of considerable interest in public key cryptography. They are not much used these days, but are of high historial importance.

If we take a sequence of positive integers B, with a super-increasing property: B = ⟨b₁, …, b_{N - 1}, b_N⟩, that is b₂ > b₁, b₃ > b₂ = b₁, or generically, b_N > ∑^{N - 1}_{j = 1} b_j.

If we suppose we have a plaintext N-bit sequence p₁…p_{N - 1}p_N, we encrypt this by E(p) = ∑^N_{j = 1} p_jb_j, but the plaintext can be easily recovered.

Example in lecture 14
slide 8.

By considering each value of the knapsack in decreasing order we can consider whether or not it can possibly exist in the final solution, and therefore whether the corresponding value of the key is 1 or 0.

In order to strengthen this, we can hide the super-increasing property of a sequence by transforming it in some way or another. If we start with a super-increasing knapsack B′ = ⟨b′₁, …, b′_{N - 1}, b′_N⟩ and two integers (m, p) with no factors in common. A new knapsack is now formed: B = ⟨b₁, …, b_{N - 1}, b_N⟩, b_i = m × b′_i mod p. This new knapsack is non-super-increasing.

Encryption is done as before with the new knapsack: C = E(p) = ∑^N_j=1 p_jb_j.

To decrypt, we assume we can find an inverse to m such that m × m^-1 = 1 mod p, then we can calculate:

Cm^-1 mod p = ∑^N_j=1 p_jb_jm^-1 mod p
Cm^-1 mod p = ∑^N_j=1 p_jb′_jmm^-1 mod p
Cm^-1 mod p = ∑^N_j=1 p_jb′_j mod p

The final form is super-increasing.

Euclid's algorithm for greatest common divisor

Real knapsacks may have hundreds of elements. The methods of attack aren't detailed here, but there have been many knapsack variants, and virtually all have been broken. Schneir says "There have all been analysed and broken, generally using the same techniques, and litter teh cryptographic highway".

See GRA.

We can use tests of graph isomorphism to apply this protocol to cryptography. Graph isomorphism is a very hard problem in general and we can use this fact to allow us to demonstate knowledge of an isomorphism without revealing the isomorphism itself.

If we start with two isomorphic graphs G and G′, then Peggy generates a random isomorphism H of G and sends it to Victor. Victor then asks Peggy to prove H is isomorphic to G, or H is isomorphic to G′.

If Peggy knows the secret mapping f she is able to respond appropriately to either of these requests. For the G case, she just sends the inverse q of the random isomorphism p. For the G′ case, she responds with r = q;f. This is repeated as in the example above.

Given a matrix A_{m × n} where a_ij = ±1, find a vector S_n where s_j = ±1, so that in the vector A_{m × n}S_{n × 1}, w_n ≥ 0.

This problem could be made harder to imposing an extra constraint, so A_{m × n}S_{n × 1} has a particular histogram H of positive values.

The suggested method to generate an instance is to generate a random matrix A, and then a random secret S, and then calculate AS. If any (AS)_i < 0, then the ith row of A is negated.

However, there is significant structure in this problem, as there is a high correlation between the majority values of the matrix columns and the secret corresponding secret bits. Each matrix row/secret dot product is the sum of n Bernouilli variables. The intial histogram has Binomial shape, and is symmetric about 0, and after negation this simply folds over to be positive.

To solve the perceptron problem, we can use search to search the space of possible secret vectors (Y) to find one that is an actual solution to the problem at hand.

We first need to define a cost function, where vectors that nearly solve the problem have a low cost, and vectors that are far from solving the problem have a high cost. We also need to define a means of generating neighbours to the current vector, and a means to determine whether to move to that neighbour or not.

Pointcheval couched the perceptron problem as a search problem. The neighbourhood is defined by single bit flips on the current solution (Y), and the cost function punishes any negative image components.

A solution to this permuted Perceptron Problem (where a Perceptron Problem solution has a particular histogram) is also a Perceptron Problem solution. Estimates of cracking the permuted Perceptron Problem on a ratio of Perceptron Problem solutions to the permuted Perceptron Problem solutions were used to calculate the size of the matrix for which this should be the most difficult: (m, n) = (m, m + 16).

This gave rise to estimates for the number of years needed to solve the permuted Perceptron Problem using annealing as the Perceptron Problem solution means that instances with matrices of size 200 could usually be solved within a day, but no Pointcheval problem instance greater than 71 was ever solved this way, despite months of computation.

Knudsen and Meier carried out a new approach in 1999, that loosely carried out sets of runs, and noted the positions where the results obtained all agree. Those elements where there is complete agreement is fixed, and new sets of runs are carried out. If repeated runs give some values for particular bits, the assumption is that those bits are actually set correctly.

This sort of approach was used to solve instances of the Perceptron Problem up to 180 times faster than the previous mechanism.

This approach is not without its problems, as not all bits that have complete agreement are correct.

An enumeration stage is used to search for the wrong bbits, and a new cost function with w₁ = 30 and w₂ = 1 is used with histograph punishment: cost(y) = w₁costNeg(y) + w₂costHist(y).

What limits the ability of annealing to find a solution? A move changes a single element of the current solution, and we want current negative image values to go positive, but changing a bit to cause negative values to go positive will often cause small positive values to go negative (as it is near in the simulated annealing).

Results can be significantly improved by punishing at a positive value, which drags elements away from the boundary during the search. Using a higher exponent in differences (e.g., |w_i - k|², where k is the boundary, e.g., 4) rather than simple deviation.

With this, we can use a similar cost function as Knudsen and Meier, but with fault injection on the negativity part (and different exponents).

cost(Y) = G∑^m_{i = 1} (max{ K - (AY)_i, 0 })^R + ∑ⁿ_{i = 1} (| H_y(i) - H_s(i) |)^R.

Each problem instance is attacked using a variety of different weightings (G), bounds (K) and values of the exponent (R). This resutls in a number of different viewpoints on each problem.

The consequence is that the warped problems typically give rise to solutions with more agreement to the original secret than the non-warped ones. However, results may vary considerably, even between runs for the same problem.

Democratic viewpoint analysis is used, as it is essentially the same as Knudsen and Meier as before, but this time substantial rather than unanimous aggreement. If we choose the amount of disagreement which is tolerated carefully, we can sometimes get over half the key this way.

A lot of information is thrown away, but if we monitor the search process as it slows down we can profile annealing and gain information from the timing.

This is based on the notion of thermostatistical annealing. Analysis shows that some elements will take some values early in the search and then never subsequently change (i.e., they get stuck). These ones that get stuck early often do so for a good reason - they are the correct values.

Timing profiles of warped problems can reveal significant information; the trajectory by which a search reaches its final state may reveal more information about the sought secret than the final state of the search.

Multiple clock watches analysis is essentially the same as for timing analysis, but this time the times of all runs where each bit got stuck is added up. As we might expect, those bits that often get stuck early (i.e., have low aggregate times to getting stuck) generally do so at their correct values (they take the majority value). This seems to have a significant potential, but needs some work.

Many crypto algorithms calculate R = y^k mod m, where y is the plaintext and k is the secret key, however exponentiation is often very large and is broken down to be more efficient.

Examples on slide 9
of lecture 11.

In base 2, if we let the binary expression of the n-bit key k be k_{n - 1}…k₁k₀, then x^k = y^{k₀k₁…k_n-1} = (…((y^k₀)² × y^k₁)² … )² × y^{k_{n - 1}}.

Similarly for modulo arithmetic, in general (x × Y) mod m = ((x mod m) × (y mod m)) mod m.

With this we can develop an algorithm for modular exponentiation:

s0 := 1
for i = 0 to n-1:
    Ri := (if ki = 1 then (s1 × y) mod m else si)
    si + 1 := (Ri × Ri) mod m
return Rn-1

We assume the attacker knows the total time to execute the algorithm for several unknown k. We notice above that the algorithm performs key-dependent multiplications, that is, it does when k_i = 1, but not when k_i = 0 (from line 4 of the algorithm). So, given a range of k, the attacker can collect enough information to deduce the Hamming weight (number of 1s) of each key.

This isn't very interesting, because the Hamming weight is normally approximately n/2. It is also easily blinded, by doing dummy calculations when k_i = 0, e.g.,

d := (si × y) mod m
Ri := (if ki = 1 then d else si)

We can do a better attack in the same theme. If we assume the attacker knows the total time to execute the algorithm for a givem m and several known y: {(y₁, t₁), …, (y_{n, tn)}, then the data-dependent time take to perform each multiplication comes from the code:} Ri := (if ki = 1 then (si × y) mod m else si)
si+1 := (Ri × Ri) mod m

We notice that the time for each multiplication is depdendent on s_i, and hence on the key bits k_i…k₀ used so far.

Different ys result in different calculations, which will take different times, so the measured total times for the different y have a variance: σ² = 1/N ∑^N_{i = 1}(t_i - μ)².

The attack then emulates the algorithm for each y_i. As we have assumed the attacker knows the data-dependent multiplication times, the attacker can caculate how long each round takes, assuming a key-bit value.

The first step is to calculate the time for the i = 0 loop twice, getting getting t_{k = 0} by assuming that k₀ = 0 and t_k=1 for k₀ = 1, and then subtract the calculated time from the measured t_i.

We can now calculate new variances of the remaining times. On average, one of the new variances is higher, and one lower than the original: σ_{k = 0}² < σ² < σ_{k = 1}², or, σ_{k = 1}² < σ² < σ_{k = 0}².

The smaller variance indicates the correct choice of key bit, as the correct guess subtracts off the correct times, leaving less variation in the remaining times (one algorithm loop fewer of different timings). An incorrect guess subtracts off an arbitrary time, increasing the variation in the timings.

This can then be interated. The attack progresses bit by bit, subtracting the times for the relevant calculations and the result of the previous key bit guesses. If a mistake is made, the variances start to increase (even if subsequent key bit guesses are correct, because of the wrong value of s_i being used in the timing calculations), indicating the attack should backtrack.

This continues until the whole key is revealed.

This attack is computationally feasible (it progresses one bit at a time), is self-correcting as erroneous guesses become apparent, and works against many obvious blinding defences (but not all).

Time is not the only resource consumed by implementations; they all require some form of power, and unsurprisingly monitoring power consumption can reveal secret key information too.

To measure the power consumption of a circuit, a small (50 Ω) resistor is placed in series with the power or ground input. The voltage difference across the resistor can be used to give current (V/R=I). A well-equiped electronics lab can sample at over 1 GHz with less and 1% error, and sampling at 20 MHz or faster can now be done quite cheaply.

Simple Power Analysis

Differential Power Analysis