==Phrack Inc.== Volume 0x0b, Issue 0x3e, Phile #0x0e of 0x10 |=---------=[ A Dynamic Polyalphabetic Substitution Cipher ]=------------=| |=-----------------------------------------------------------------------=| |=----------------=[ Veins ]=--------------------=| 1 - Introduction 1.1 - First of all, a reminder. What is polyalphabetic substitution ? 1.2 - Weaknesses in polyalphabetic substitution 2 - IMPLEMENTATION OF DPA-128 2.1 - DPA-128 used as a one way hash function 2.2 - DPA-128 used as PRNG 3 - Acknowledgment 4 - References 5 - Source Code --[ 1 - Introduction In Phrack #51, mythrandir discussed the cryptanalysis of monoalphabetic ciphers and basic substitutions and transpositions. This paper discusses a different substitution known as 'polyalphabetic substitution' and how some mechanisms can be implanted to take advantage of its characteristics. This document will then focus on 'dynamic polyalphabetic substitution' which is an evolution of polyalphabetic substitution with key-dependant s-tables. A "functional-but-still-work-in-progress" cipher will be presented. It is a 128-bits secret-key block cipher that uses polyalphabetic s-tables which are highly dependant of the key. The cipher, DPA-128, consists in a simple function that makes 3 operations on the block. It is not a Feistel network but still respects Shannon's principles of diffusion and confusion. It has only been reviewed by a few people, so I strongly discourage its use as it has not proven anything yet. However, if you use it and have any comments, I'd be glad to hear from you, but remember, do not encrypt sensitive stuff cause someone will probably come, break the cipher and go spreading all of your secrets on IRC ;) Finally, just to clarify a few things. I use the acronym DPA (for "dynamic polyalphabetic algorithms") in this document to refer to key dependancy in polyalphabetic substitution. I've seen people using the term "dynamic" for ciphers that used polyalphabetic substitution in a mode that uses a pseudo random vector (CBC for example). While I'll keep using the acronym, assume that key-dependant substitution works in total abstraction of the mode and DPA-128 has an implementation of both ECB and CBC modes as I'm writing. Also, while I have not seen a dynamic polyalphabetic cipher implementation it does not mean that all of the ideas in this paper are new. DES had some variants that performed key-dependant substitutions by exchanging lines of s-tables, and several ciphers use one-way hash functions for subkeys. ----[ 1.1 - First of all, a reminder. What is polyalphabetic substitution ? Polyalphabetic substitution is an hybrid between transposition and substitution. Transposition consists in reordering the characters in the plaintext to produce the cipher: Assume my secret message is: THIS IS MY SECRET MESSAGE DONT READ IT, ARAM SUCKS After transposing it in a 8 columns table, it becomes: T H I S I S M Y S E C R E T M E S S A G E D O N T R E A D I T A R A M S U C K S The cipher is produced by reading the columns instead of the lines: TSSTR HESRA ICAEM SRGAS IEEDU STDIC MMOTK YENAS While substitution consists in interchanging the characters in the plaintext to produce the cipher: Assume my secret message is: THIS IS ANOTHER ATTEMPT TO PRESERVE MY PRIVACY Substitution alphabet is a simple rearrangement: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Y Z W X U V S T Q R O P K L M N I J G H E F C D A B The cipher is produced by replacing the letter in plaintext by the new letter in the rearranged alphabet: HTQG QG YLMHTUJ YHHUKNH HM NJUGUJFU KA NJQFYWA Note that both these methods do not even require a key, the parties that wish to share the secret, have to share the "protocol" which is the number of columns for the transposition, or the rearranged alphabet for the substitution. In practice, there are methods to use keys with both substitution and transposition but in the end, both are insecure with or without a key. I won't go through the description of how you can break these, the methods were described in phrack #51 if I recall correctly and they are so simple that some tv magazines use these on their game pages. Now let's get back to polyalphabetic substitution. A transposed substitution table looks like this more or less: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z A B C D E F G H I J K L M N O P Q R S T U V W X Y This is known as the "Vigenere Table", because it was invented by Blaise Vigenere (a French mathematician, if you care). Unlike transposition and substitution, a key is required. Assume my secret key is: BLEH Assume my secret message is: LAST ATTEMPT The ciphertext is the intersection of each character of the secret key with each character of the secret message. Key characters are seeked on the very first line, and message characters are seeked on the very first column. Since the key is shorter than the message, it is padded with itself so that it becomes: BLEHBLEHBLE If it was longer, then either the message would be padded with random crap or the key would be truncated (this is more common). The cipher is obtained by replacing a letter in the message by the intersection of current message character and current key character in the table. The secret message becomes: MLWABUXLNAX As you may notice, even though a character may appear two or more times in the plaintext, it is not encrypted the same way in the ciphertext depending on which character from the key is used for the substitution. This is what "polyalphabetic" means in "polyalphabetic substitution". It was known for a while as the "unbreakable cipher" and a variant was used successfuly during Second World War by the Resistance against the Germans. While this sounds stronger than transposition and substitution, it is still very weak and unless a RNG is used to generate a key that is as long as the data to encrypt (one-time pad), it is possible to recover the key size, the key itself and/or the message with enough data to analyze. The methods used to break this kind of cipher is out of the scope of this paper but a search on google will give you enough hints ;) Polyalphabetic tables have three interesting properties: a) f(a, b) == c f(a, b) == f(b, a) but... f(a, c) != b and assuming c = f(a, b), then there is a f1 such as f1(a, c) == b b) using the ASCII layout, there are 256^2 combinations which will produce 256 possible results (including the original character). c) if we assume that the key is truly random AND has the same size as the message to encrypt, then all results are equiprobable. and equiprobability means that: - if you only take one character in the ciphertext, then you have as many chances for it to be any cleartext character. They all appear the exact same number of times in the table and are the result of as many combinations each. - there is no "useless" substitution. If substitution of character 'A' results in character 'A', then it is not considered as a useless substitution as it had as many chances to be out than any other. ----[ 1.2 - Weaknesses in polyalphabetic substitution As I previously said, the above cipher is weak. The weaknesses are numerous and mostly related to the cipher leaking informations about the cleartext, the key and/or the substitution table. If one can encrypt data using the same key, he can determine the size of the key with one message and determine the structure of the substitution table with another, giving him all the necessary information to understand the ciphertext and any other ciphertext encrypted using the same key. But don't get this wrong, he doesn't HAVE to be able to encrypt data, this is just a convenience ;) The fact that the key is concatenated to itself does not make a change, and actually an implementation on computer would work on data using a modulo on the size of the key to save memory. The reasons why it is so easy are described here: - if one chooses a key A and a key B such as they only differ by one bit, then the ciphertext will only differ by one byte. - if one chooses a message A and a message B such as they also only differ by one bit, then the ciphertext will differ by one byte. - if one changes one bit in ciphertext and decrypts it, the resulting message will only differ by one byte. - if one has partial knowledge of the key, or of the message, then he can determine which substitutions are not probable and therefore reduce drastically the complexity of an attack. Also partial knowledge of the key or the message gives statistical analysis a chance to break the ciphertext when polyalphabetic substitution had all the characteristics needed to prevent that from happening. So... let's sum things up. Polyalphabetic substitution as described above is vulnerable to chosen texts attack, known texts attack, key correlation attack and eventually statistical attacks. Oh... almost forgot... any partial information reveals information about other unrelated data. If I partially know the plaintext, then with access to the ciphertext I am able to recover partially the key, with partial knowledge of the key and access to the ciphertext, i am able to recover partially the plaintext. There is not one point of failure, there are only points of failures... ----[ 1.3 - Theory of information Shannon described two properties that a block cipher should have in order to be strong. Not that all ciphers respecting these are strong, but those that do not respect it are most likeley weak. These properties are 'confusion' and 'diffusion'. The first one is what we achieve with polyalphabetic substitution, incapacity to deduce from a single encrypted byte, with no other information, the result of which substitution it is. This is because of the equiprobabiliy polyalphabetic tables gives us. The second is diffusion, which is lacking from the above cipher, and one of the reason why it is so vulnerable. Diffusion is a characteristic where a minor cause produces a major result. It is sometimes called 'cascading effect'. Basically, diffusion should ensure that a one-bit change in the key alters the whole ciphertext, that a one-bit change in the plaintext also alters the whole ciphertext and that a one-bit change in the ciphertext alters the whole plaintext. This complete alteration is only in appearance, and a better look at the complete ciphertext would reveal an average of half bits modified as you'll notice in the output of `bitdiff` later in this paper. While it is difficult to decide wether or not a cipher has a correct confusion and diffusion, they both produce an entropic result that can be measured using several methods. These methods will be used in this paper but explained further in the references. A cipher not producing true entropy is weak, true entropy (== white noise). One way to add confusion is to ensure that the ciphertext is not dependant of the key on a character basis. Changing one bit of the key should change the whole ciphertext. This can be achieved by the use of a one-way hash function for key generation. Some one-way hash functions have properties that make them suitable for use, these are: h = f(M) - no matter the length of M, h has a fixed size - assuming M, it should be easy to compute h - assuming h, it should be difficult to compute M - a one-bit change in M alters half the bits in h (in average). - it should be hard to find a M' to a fixed M such as f(M) = f(M') - it should be hard to find any M and M' such as f(M) = f(M') The two last properties seem to be identical but in practice it is "easier" to produce a random collision, than to produce a collision for an expected output. Assuming h is 128-bits long, finding a particular collision takes at most 2^128 tries, while finding a collision takes at most 2^64 tries. This is known as the anniversary attack. The use of such a function will make key correlation hardly practicable as choosing two keys that have a relation will result in subkeys that have no relation at all, even if the relation is a single bit difference. I am not even mentionning attacks based on partial knowledge of the key ;) Also, this will prevent users from choosing weak keys, purposedly or not, as it will be difficult to find a key that will produce a weak key (assuming that there are weak keys ;) once passed throught the one-way hash function. By weak key, I do not mean keys like "aaaa" or "foobar", but keys that will produce a subkey that introduces a weakness in the encryption process (such as DES's four weak keys). The function not being reversible, partial knowledge of plaintext and access to ciphertext does not reveal the key but the subkey from which you cannot obtain information about the key. If the algorithm iterates for several rounds, it is possible to generate subkeys by calling f on previous subkey: round1: f(k) round2: f(f(k)) round3: f(f(f(k))) and so on... Note that there is nothing that prevents an implementation from precomputing the subkeys for better performances (this is what my implementation does) instead of computing them for each block. The characteristics remains, knowing the subkey for round3 does not give information about the subkey used for round2 or round1. That is one of the failure points plugged ;) Finally, this will increase confusion by creating a relation between each single bit of the user input key and each byte of the ciphertext. Unfortunately, this is not enough. We added confusion but even though it is theoritically not possible to retrieve the key, even by having access to the full message and the full ciphertext, it is still possible with a partial knowledge to retrieve the subkey and to decrypt any data that is encrypted with the original key. This is where diffusion comes into play with a method called 'byte chaining'. Byte chaining is to a block what block chaining is to a ciphertext, a propagation of changes which will affect all subsequent data. This is done with a simple Xor, where each byte of the block is xor-ed with the next one (modulo size of the block to have the last one be xor-ed with the first one). That way, a single bit change in a byte will have repercussion on every byte after that one. If the function used to encrypt data is called for more than one round, then all bytes are guaranteed to have been altered by at least one byte. This operation is done before encryption so that the result of an encrypted byte is dependant not only of the current byte but of all the ones that were used for the byte chaining. As rounds occur, cascading effect takes place and the change propagates through the block. It is possible to increase complexity by using a key-related permutation before encryption. DPA-128 uses a key-related shifting instead but this can be considered as a permutation in some way. Some functions known as 'string hash functions' can compute an integer value out of a string. They are commonly used by C developpers to create hash tables and they are pretty simple to write. It is possible to use these functions on a subkey to create a key-related circular shifting within the block: - we have a subkey for the round that we computed using f, this subkey is hashed to produce an integer. the hash function does not have to respect any constraints because of f properties. the paranoiac could implement a function that has low collisions and a nice repartition but since it is applied on the result of f, it inherits some of its characteristics. - assuming the block size is 128, we reduce that integer to 128 (7 bits) there is no magic stuff here, just a modulo. - the result is used to shift the block circularly >>> Note that the key-relation for the shifting has no more security than a simple byte shifting - at least on Vigenere table - but only adds more confusion. It was initially introduced as a security measure for substitution tables that had not equiprobable results. It prevents elimination of some substitution combinations by analyzing which bits are set in an encrypted byte when you know its plaintext equivalent. From the ciphertext, it is not possible to determine wether a block was shifted (the hash value of the key could have been 0 or some product of 128, who knows ;) and if it was shifted, it is not possible to know where the bits come from (which byte they were on originally and what was their position) which makes it difficult to determine if the bit of sign on a particular byte is really a bit of sign or not and if it was part of that byte or not. Also, the shifting is dependant from the subkey used for a round so it will be different at each round and help diffusion through the byte chaining phase. Finally, it is possible, using the same method, to create a relation between a subkey and the substitution table. This is where dynamic polyalphabetic substitution comes into play ! As we've seen, a polyalphabetic substitution has 256^2 substitutions with 256 outcomes. This means that if an attacker would want to try all combinations possible, he would have to try 256 combinations for a character to be sure the right couple was used (if he knew the structure of the substitution table, or 256^2 otherwise). It is possible to increase that value by creating a relation between the key and the substitution table. There are 256 characters, so it is possible to create 256 different tables by shifting ONE byte on each line: instead of: 0 1 2 3 4 5 6 7 8 9 ... 1 2 3 4 5 6 7 8 9 ... 2 3 4 5 6 7 8 3 4 5 6 7 8 4 5 6 7 8 5 .... ... we end with (n being the shift): n%256 (n+1)%256 (n+2)%256 (n+3)%256 (n+4)%256 (n+5)%256 ... (n+1)%256 (n+2)%256 (n+3)%256 (n+4)%256 (n+5)%256 ... (n+2)%256 (n+3)%256 (n+4)%256 (n+5)%256 (n+6)%256 (n+3)%256 (n+4)%256 (n+5)%256 (n+6)%256 (n+7)%256 (n+4)%256 (n+5)%256 (n+6)%256 (n+7)%256 (n+8)%256 (n+5)%256 (n+6)%256 (n+7)%256 (n+8)%256 (n+9)%256 (n+6)%256 ... ... This means that an attacker would need to try 256^2 combinations before he knows for sure the right combination was used. he needs to try the same combinations as before but with every variation of 'n'. 'n' can be computed using the same method as for the block shifting but since there are 256 possible shifts for the substitution table, then the result will be reduced modulo 256 (8 bits). The tables being structured in a logical way, they can be represented by arithmetics which removes the need to store the 256 possible tables and saves quite a bit of memory. It is also possible with more work to create polyalphabetic s-tables that are shuffled instead of shifted, such tables would still share the characteristics of polyalphabetism but prevent partial knowledge of the table from deducing the full internal structure. I did not have enough time to keep on working on this so I am unable to give an example of these, however, simple tables such as the one above is sufficient in my opinion. k being the character from the key, d being the character from the message and s being the shifting. encryption can be represented using this equation: (k + d + s) mod 256 while decryption is: ((256 + d) - k - s) mod 256 The amusing part is that when you play with statistics, you get a very different view if you are in the position of the attacker or of the nice guy trying to keep his secret. Assuming there are 'n' rounds, then you have (256^2) * m substitutions useable where 1 <= m <= n and n <= 256. This is because some subkeys might produce identical substitution tables. In another hand, and im not doing the maths for this ;), the attacker has not only to figure out which substitutions were done, but also the tables in which they were done... in the exact same order... out of data that does not inform him on the subkeys used to generate the tables he is trying to determine the structure of ;) The result is NOT equiprobable, because it would require exactly 256 rounds with different tables which is hardly doable (just determining if it is doable requires trying 2^128^256 keys if im correct), but from the attacker point of view, even an exhaustive search might create an indecision because many keys will probably result in the same cipher if applied to different messages (many will produce the same cipher if applied to garbage too ;). --[ 2 - IMPLEMENTATION OF DPA-128 As I said, DPA-128 is a secret-key block cipher. Its block and key size are 128-bits. This is not a limitation imposed by the algorithm which is easily adaptable to different key and block sizes. It consists of 16 rounds, each performing: - a byte chaining; - a subkey-related shifting; - a subkey-related polyalphabetic substitution; All of the rounds have their own subkey. The implementation uses all of the ideas explained in this paper and before I provide the code, here are a few tests performed on it. ----[ 2.1 - DPA-128 used as a one way hash function Bruce Schneier explained in "Applied Cryptography" that some ciphers can be turned into one way hash functions by using them in BC modes (CBC for that matter) using a fixed key and initialization vector with more or less efficiency. It is hard to determine if DPA-128 is efficient because it was not been analyzed by many people and I consider it as efficient to produce checksums as to encrypt. If there is a weakness in the cipher then the checksum will not be secure. The same applies to DPA-128 used as a PRNG. So... I did some testing ;) I used three tools, the first one 'bitdiff' is a little utility that goes through two files and compares them bit per bit. It then outputs the number of bits that have changed and the repartition of zero's and one's. A sample output looks like this: % ./bitdiff file1 file2 64 bits have changed. ratio for file1: 0's: 55 1's: 73 ratio for file2: 0's: 71 1's: 57 I also used a tool 'segments', which counts segments of identical bits in a file. A sample output looks like this: % ./segments file1 0's segments: 1 => 19 2 => 6 3 => 4 4 => 0 1's segments: 1 => 13 2 => 7 3 => 3 4 => 3 Finally, I used an existing tool called 'ent' which is available at http://www.fourmilab.ch/random/ which performs several entropy tests, helping determine: - if DPA-128 passes deterministic tests and how does it compare to a PRNG (I used NetBSD's /dev/urandom). - what is the impact to a checksum when a bit changes in a file. Theoritically, an equiprobable cipher would not be a nice idea for a one-way hash function as it would be easily subject to collisions, but as I explained, the result seems to be equiprobable while there is a limited range of possible substitution for a fixed key. I checksum-ed /etc/passwd three times, the first one was the real file, the second one was the file with a one bit change and the third one was the file with a 6 bytes addition. All bytes where affected, tests with bitdiff showed that a one bit change produced an average of 60 bits modified in the 128 bits checksum. % ./dpa sum passwd |hexdump 0000000 be85 3b72 1a76 48e6 5d08 939b 104f 3f23 0000010 % ./dpa sum passwd.1 | hexdump 0000000 f9d3 c5fe d146 2170 144d 900d 0e99 c64b 0000010 % ./dpa sum passwd.2 | hexdump 0000000 fa19 4869 3f61 798a 2e81 91e9 bc92 78ee 0000010 After i redirected the checksums to files, i call bitdiff on them. The files do not contain the hexadecimal representation, but the real 128 bits outputs: % ./bitdiff passwd.chk passwd.1.chk 63 bits have changed. ratio for passwd.chk: 0's: 65 1's: 63 ratio for passwd.1.chk: 0's: 68 1's: 60 % ./bitdiff passwd.chk passwd.2.chk 61 bits have changed. ratio for passwd.chk: 0's: 65 1's: 63 ratio for passwd.2.chk: 0's: 64 1's: 64 You'll notice a nice repartition of zero's and one's, lets' see what segments has to say about this: % ./segments passwd.chk 0's segments: 1 => 13 2 => 10 3 => 3 4 => 2 1's segments: 1 => 15 2 => 4 3 => 5 4 => 0 % ./segments passwd.1.chk 0's segments: 1 => 11 2 => 8 3 => 5 4 => 3 5 => 0 1's segments: 1 => 13 2 => 9 3 => 2 4 => 0 5 => 1 % ./segments passwd.2.chk 0's segments: 1 => 12 2 => 10 3 => 3 4 => 1 5 => 0 1's segments: 1 => 16 2 => 3 3 => 4 4 => 3 5 => 1 Well all we can notice is that there are mostly small segments and that they are well reparted. I'm skipping the entropy test since it will illustrate the use of DPA-128 as a PRNG ;) ----[ 2.2 - DPA-128 used as PRNG For the following tests concerning segments and entropy: - the file 'urandom.seed' consists in 1024 bytes read from NetBSD 1.6.1's /dev/urandom - the file 'dpa.seed' consists in the result of an ECB encryption on dpa's main.c and a reduction of the output to 1024 bytes. This means that while tests on urandom.seed apply to the result of a PRNG, the tests on dpa.seed can be reproduced. It shows good entropy on encrypting a fixed value and the results should be quite the same if used as a PRNG. The tests that are performed by 'ent' are described on their website, I'm not going to describe them here because it is out of the scope of this paper and I would do it far less better than their page does. % ./segments urandom.seed 0's segments: 1 => 1019 2 => 418 3 => 212 4 => 88 5 => 35 6 => 18 1's segments: 1 => 1043 2 => 448 3 => 179 4 => 74 5 => 32 6 => 13 % ./segments dpa.seed 0's segments: 1 => 1087 2 => 443 3 => 175 4 => 72 5 => 29 6 => 18 1's segments: 1 => 1039 2 => 453 3 => 195 4 => 67 5 => 34 6 => 15 % ./ent -b urandom.seed Entropy = 0.999928 bits per bit. Optimum compression would reduce the size of this 8192 bit file by 0 percent. Chi square distribution for 8192 samples is 0.82, and randomly would exceed this value 50.00 percent of the times. Arithmetic mean value of data bits is 0.4950 (0.5 = random). Monte Carlo value for Pi is 3.058823529 (error 2.63 percent). Serial correlation coefficient is -0.002542 (totally uncorrelated = 0.0). % ./ent -b dpa.seed Entropy = 1.000000 bits per bit. Optimum compression would reduce the size of this 8192 bit file by 0 percent. Chi square distribution for 8192 samples is 0.00, and randomly would exceed this value 75.00 percent of the times. Arithmetic mean value of data bits is 0.5000 (0.5 = random). Monte Carlo value for Pi is 3.200000000 (error 1.86 percent). Serial correlation coefficient is -0.003906 (totally uncorrelated = 0.0). % ./ent -bc urandom.seed Value Char Occurrences Fraction 0 4137 0.505005 1 4055 0.494995 Total: 8192 1.000000 Entropy = 0.999928 bits per bit. Optimum compression would reduce the size of this 8192 bit file by 0 percent. Chi square distribution for 8192 samples is 0.82, and randomly would exceed this value 50.00 percent of the times. Arithmetic mean value of data bits is 0.4950 (0.5 = random). Monte Carlo value for Pi is 3.058823529 (error 2.63 percent). Serial correlation coefficient is -0.002542 (totally uncorrelated = 0.0). % ./ent -bc dpa.seed Value Char Occurrences Fraction 0 4096 0.500000 1 4096 0.500000 Total: 8192 1.000000 Entropy = 1.000000 bits per bit. Optimum compression would reduce the size of this 8192 bit file by 0 percent. Chi square distribution for 8192 samples is 0.00, and randomly would exceed this value 75.00 percent of the times. Arithmetic mean value of data bits is 0.5000 (0.5 = random). Monte Carlo value for Pi is 3.200000000 (error 1.86 percent). Serial correlation coefficient is -0.003906 (totally uncorrelated = 0.0). The last tests must have given you an idea of the confusion, diffusion and entropy present in a DPA-128 encrypted ciphertext. More results are available online on my webpage, I just did not want to put too much in here since they all look the same ;) --[ 3 - Acknowledgment I would like to thank a few people: k` who helped me with previous versions and some parts of dpa-128, acid, who supported my endless harassement (hey try this please !), pitufo for being the first dpa-128 tester and benchmarker, hypno for reading this and spot bad sentences :) br1an for reading this also and giving advices, a ph.d whose name will remain private who audited dpa-128 and mayhem who both suggested to write a paper about dpa. --[ 4 - REFERENCES . http://www.tristeza.org/projects/dpa/ my page for the dpa project with examples and a lot of testing . http://www.csua.berkeley.edu/cypherpunks/ cypherpunks . http://www.fourmilab.ch/random/ entropy tests and their description . http://www.schneier.com/paper-blowfish-fse.html a paper on blowfish and what features a cipher should provide . "applied cryptography", Bruce Schneier THE book ;) --[ 5 - Source Code All of the code is provided under the ISC license, do whatever you want with it, but please please don't use it to encrypt sensitive data unless you know what you are doing (that means you could not break it and have confidence in your skills). The code is NOT optimized for speed, it is a work in progress and many parts can be improved, i'm just a bit in a hurry and by the time you read this, it will probably be a lot cleaner ;) If you plan on using dpa-128 even though I'm still warning you not to, here are a few recommandations: - the following code accepts keys both as parameter or as file. It is preferable for many reasons to use a file, but the best reason (aside from someone issueing a `ps` at the wrong moment...) is that you can have your key be the result of a PRNG: % dd if=/dev/urandom of=/home/veins/.dpa/secret.key bs=1024 count=1 The odds of someone guessing your key become pretty low :) - use CBC mode. the impact of using CBC mode on performances is too low to be an excuse for not using it. To encrypt: % dpa -a enc -m cbc -k file:secret.key -d file:/etc/passwd -o p.enc To decrypt: % dpa -a dec -m cbc -k file:secret.key -d file:p.enc -o p.dec /* * Copyright (c) 2004 Chehade Veins * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* bitdiff.c */ /* * This is a small utility to compare the bits in two files. It is ugly * and could be rewritten in a sexier way but it does its job so no * need to waste time on it ;) * */ #include #include #include #include int main(int argc, char *argv[]) { int i; int size1, size2; /* size counters */ char *s1, *s2; int s1_0, s1_1; /* in s1: 0s and 1s counter */ int s2_0, s2_1; /* in s2: 0s and 1s counter */ int fd1, fd2; unsigned int cnt; unsigned int diff; unsigned int total; struct stat sa; struct stat sb; if (argc < 3) return (EX_USAGE); fd1 = open(argv[1], O_RDONLY); fd2 = open(argv[2], O_RDONLY); if (fd1 < 0 || fd2 < 0) return (EX_SOFTWARE); fstat(fd1, &sa); fstat(fd2, &sb); size1 = sa.st_size; size2 = sb.st_size; s1 = mmap(NULL, sa.st_size, PROT_READ, MAP_PRIVATE, fd1, 0); s2 = mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd2, 0); if (s1 == (void *)MAP_FAILED || s2 == (void *)MAP_FAILED) return (EX_SOFTWARE); s1_1 = s2_1 = s1_0 = s2_0 = diff = total = 0; while (size1 && size2) { for (i = 7, cnt = 0; i >= 0; --i, ++cnt) { if (((*s1 >> i) & 0x1) != ((*s2 >> i) & 0x1)) ++diff; if ((*s1 >> i) & 0x1) ++s1_1; else if (((*s1 >> i) & 0x1) == 0) ++s1_0; if ((*s2 >> i) & 0x1) ++s2_1; else if (((*s2 >> i) & 0x1) == 0) ++s2_0; ++total; } ++s1; ++s2; size1--; size2--; } if (diff == 0) printf("bit strings are identical\n"); else { printf("%d bits have changed.\n", diff, total); printf("ratio for %s:\n", argv[1]); printf("\t0's: %d\n", s1_0); printf("\t1's: %d\n", s1_1); printf("\n"); printf("ratio for %s:\n", argv[2]); printf("\t0's: %d\n", s2_0); printf("\t1's: %d\n", s2_1); } munmap(s1, sa.st_size); munmap(s2, sb.st_size); return (EX_OK); } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* segments.c */ /* * This is a small utility to count the segments of identical bits in a * file. It could also be rewritten in a sexier way but... * */ #include #include #include #include int main(int argc, char *argv[]) { int i; int fd; int cnt; int last; int biggest; int size; char *map; struct stat sb; unsigned int STATS[2][32]; if (argc < 2) return (EX_USAGE); /* Initialize the segments counters */ for (cnt = 0; cnt < 2; ++cnt) for (i = 0; i < 32; ++i) STATS[cnt][i] = 0; /* Open and map the file in memory */ fd = open(argv[1], O_RDONLY); if (fd < 0) return (EX_SOFTWARE); fstat(fd, &sb); map = mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0); if (map == (void *)MAP_FAILED) return (EX_SOFTWARE); last = -1; biggest = 0; size = sb.st_size; while (size--) { for (i = 7, cnt = 0; i >= 0; --i, ++cnt) { if ((*map >> i) & 0x1) { if (last == 0) { if (cnt > biggest) biggest = cnt; if (cnt >= 32) errx(EX_SOFTWARE, "This cannot be an entropy source ;)"); STATS[last][cnt] += 1; cnt = 0; } last = 1; } else { if (last == 1) { if (cnt > biggest) biggest = cnt; if (cnt >= 32) errx(EX_SOFTWARE, "This cannot be an entropy source ;)"); STATS[last][cnt] += 1; cnt = 0; } last = 0; } } ++map; } munmap(map, sb.st_size); printf("0's segments:\n"); for (i = 1; i < biggest; i++) printf("\t%d => %d\n", i, STATS[0][i]); printf("\n1's segments:\n"); for (i = 1; i < biggest; i++) printf("\t%d => %d\n", i, STATS[1][i]); return (EX_OK); } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - Again, the source code that follows is a work in progress, and some parts deserve a cleaner rewrite. data.c is truly ugly ;) It was tested on Linux & BSD/i386, SunOS/sparc and OSF1/alpha, if it does not run on your unix box, porting it should be trivial. 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - # Makefile NAME = dpa SRCS = main.c\ bitshift.c\ bytechain.c\ blockchain.c\ E.c\ D.c\ S_E.c\ S_D.c\ iv.c\ ecb.c\ cbc.c\ checksum128.c\ hash32.c\ key.c\ data.c\ sum.c\ usage.c OBJS = $(SRCS:.c=.o) CFLAGS = LDFLAGS = $(NAME) : $(OBJS) cc -o $(NAME) $(OBJS) $(LDFLAGS) clean : rm -f *.o *~ fclean : clean rm -f $(NAME) re : fclean $(NAME) 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* include/dpa.h */ #ifndef _DPA_H_ #define _DPA_H_ #define DPA_KEY_SIZE 16 #define DPA_BLOCK_SIZE 16 #define DPA_ENCRYPT 0 #define DPA_DECRYPT 1 #define DPA_MODE_ECB 0 #define DPA_MODE_CBC 1 struct s_dpa_sub_key { unsigned char key[DPA_KEY_SIZE]; unsigned char shift; }; typedef struct s_dpa_sub_key DPA_SUB_KEY; struct s_dpa_key { struct s_dpa_sub_key subkey[16]; }; typedef struct s_dpa_key DPA_KEY; struct s_dpa_data { unsigned char *data; unsigned long length; }; typedef struct s_dpa_data DPA_DATA; void checksum128(unsigned char *, unsigned char *, unsigned int); unsigned long hash32(unsigned char *, unsigned int); unsigned char dpa_encrypt(unsigned int, unsigned int, unsigned int); unsigned char dpa_decrypt(unsigned int, unsigned int, unsigned int); void DPA_ecb_encrypt(DPA_KEY *, DPA_DATA *, DPA_DATA *); void DPA_ecb_decrypt(DPA_KEY *, DPA_DATA *, DPA_DATA *); void DPA_cbc_encrypt(DPA_KEY *, DPA_DATA *, DPA_DATA *); void DPA_cbc_decrypt(DPA_KEY *, DPA_DATA *, DPA_DATA *); void DPA_sum(DPA_KEY *, DPA_DATA *, DPA_DATA *); void DPA_set_key(DPA_KEY *, unsigned char *, unsigned int); void DPA_set_keyfile(DPA_KEY *, char *); void DPA_set_data(DPA_DATA *, unsigned char *, unsigned int); void DPA_set_datafile(DPA_DATA *, char *); void DPA_set_ciphertext(DPA_DATA *, DPA_DATA *, int, int); void DPA_write_to_file(DPA_DATA *, char *); void DPA_sum_write_to_file(DPA_DATA *, char *); void rbytechain(unsigned char *); void lbytechain(unsigned char *); void rbitshift(unsigned char *, unsigned int); void lbitshift(unsigned char *, unsigned int); void blockchain(unsigned char *, unsigned char *); void IV(unsigned char *); void E(unsigned char *, unsigned char *, unsigned int); void D(unsigned char *, unsigned char *, unsigned int); void S_E(unsigned char *, unsigned char *, unsigned int); void S_D(unsigned char *, unsigned char *, unsigned int); void usage(void); #endif 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* checksum128.c */ /* NEEDS_FIX */ /* * This function creates a 128 bits (16 bytes) checksum out of a variable * length input. It has NOT been verified so it is most likely broken and * subject to collisions even though I was not able to find any myself. * * The following constraints need to be respected: * - the function has to return a 128 bits value no matter what; * - it should be difficult to determine the result by knowing the input; * - it should be difficult to determine the input by knowing the result; * - it should be difficult to find an input that will produce an identic * result as a known input; * - it should be difficult to find two inputs that will produce the same * result; * - it should be easy to compute the result of an input; * * If checksum128() happens to be broken, DPA-128 could be fixed by * replacing it with any one-way hash function that produces a 128 bits * output (MD5 comes to mind first ;). */ #define __NBROUNDS 32 void checksum128(unsigned char *key, unsigned char *skey, unsigned int size) { unsigned int cnt; unsigned int length; unsigned long a; unsigned long b; unsigned long c; unsigned long d; unsigned char *save; /* Initialization of contexts */ a = 0xdeadbeef; b = 0xadbeefde; c = 0xbeefdead; d = 0xefdeadbe; for (cnt = 0; cnt < __NBROUNDS; ++cnt) { for (length = 0, save = key; length < size; ++save, ++length) { /* each context is first summed up with the cumplement of * the current ascii character. */ a = (a + ~(*save)); b = (b + ~(*save)); c = (c + ~(*save)); d = (d + ~(*save)); /* Confusion */ /* * Context A is summed with the product of: * - cumplement of B, C and cumplement of D; * * Context B is summed with the product of: * - cumplement of C, D and cumplement of A; * * Context C is summed with the product of: * - cumplement of D, A and cumplement of B; * * Context D is summed with the product of: * - cumplement of A, B and cumplement of C; * * Every context has a repercussion on all others * including itself, and multiplication makes it * hard to determine the previous values of each * contexts after a few rounds. */ a += ~b * c * ~d; b += ~c * d * ~a; c += ~d * a * ~b; d += ~a * b * ~c; } /* Diffusion */ /* * The bytes of each contexts are shuffled within the * same context, the first byte of A becomes the last * which becomes the first. the second becomes the * third which becomes the second. This permutation * is also applied to B, C and D, just before they go * through another round. */ a = (((a & 0x000000ff) << 24) + ((a & 0x0000ff00) << 8) + ((a & 0x00ff0000) >> 8) + ((a & 0xff000000) >> 24)); b = (((b & 0x000000ff) << 24) + ((b & 0x0000ff00) << 8) + ((b & 0x00ff0000) >> 8) + ((b & 0xff000000) >> 24)); c = (((c & 0x000000ff) << 24) + ((c & 0x0000ff00) << 8) + ((c & 0x00ff0000) >> 8) + ((c & 0xff000000) >> 24)); d = (((d & 0x000000ff) << 24) + ((d & 0x0000ff00) << 8) + ((d & 0x00ff0000) >> 8) + ((d & 0xff000000) >> 24)); } /* Diffusion */ /* * The Checksum is constructed by taking respectively * the first byte of A, B, C and D, then the second, * the third and the fourth. */ skey[0] = (a & 0xff000000) >> 24; skey[1] = (b & 0xff000000) >> 24; skey[2] = (c & 0xff000000) >> 24; skey[3] = (d & 0xff000000) >> 24; skey[4] = (a & 0x00ff0000) >> 16; skey[5] = (b & 0x00ff0000) >> 16; skey[6] = (c & 0x00ff0000) >> 16; skey[7] = (d & 0x00ff0000) >> 16; skey[8] = (a & 0x0000ff00) >> 8; skey[9] = (b & 0x0000ff00) >> 8; skey[10] = (c & 0x0000ff00) >> 8; skey[11] = (d & 0x0000ff00) >> 8; skey[12] = (a & 0x000000ff); skey[13] = (b & 0x000000ff); skey[14] = (c & 0x000000ff); skey[15] = (d & 0x000000ff); } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* hash32.c */ /* * This function computes a 32 bits output out a variable length input. It is * not important to have a nice distribution and low collisions as it is used * on the output of checksum128() (see checksum128.c). There is a requirement * though, the function should not consider \0 as a key terminator. */ unsigned long hash32(unsigned char *k, unsigned int length) { unsigned long h; for (h = 0; *k && length; ++k, --length) h = 13 * h + *k; return (h); } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* bytechain.c */ #include "include/dpa.h" void rbytechain(unsigned char *block) { int i; for (i = 0; i < DPA_BLOCK_SIZE; ++i) block[i] ^= block[(i + 1) % DPA_BLOCK_SIZE]; return; } void lbytechain(unsigned char *block) { int i; for (i = DPA_BLOCK_SIZE - 1; i >= 0; --i) block[i] ^= block[(i + 1) % DPA_BLOCK_SIZE]; return; } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* bitshift.c */ #include #include "include/dpa.h" void rbitshift(unsigned char *block, unsigned int shift) { unsigned int i; unsigned int div; unsigned int mod; unsigned int rel; unsigned char mask; unsigned char remainder; unsigned char sblock[DPA_BLOCK_SIZE]; if (shift) { mask = 0; shift %= 128; div = shift / 8; mod = shift % 8; rel = DPA_BLOCK_SIZE - div; for (i = 0; i < mod; ++i) mask |= (1 << i); for (i = 0; i < DPA_BLOCK_SIZE; ++i) { remainder = ((block[(rel + i - 1) % DPA_BLOCK_SIZE]) & mask) << (8 - mod); sblock[i] = ((block[(rel + i) % DPA_BLOCK_SIZE]) >> mod) | remainder; } } memcpy(block, sblock, DPA_BLOCK_SIZE); } void lbitshift(unsigned char *block, unsigned int shift) { int i; unsigned int div; unsigned int mod; unsigned int rel; unsigned char mask; unsigned char remainder; unsigned char sblock[DPA_BLOCK_SIZE]; if (shift) { mask = 0; shift %= 128; div = shift / 8; mod = shift % 8; rel = DPA_BLOCK_SIZE + div; for (i = 0; i < (8 - mod); ++i) mask |= (1 << i); mask = ~mask; for (i = 0; i < DPA_BLOCK_SIZE; ++i) { remainder = (block[(rel + i + 1) % DPA_BLOCK_SIZE] & mask) >> (8 - mod); sblock[i] = ((block[(rel + i) % DPA_BLOCK_SIZE]) << mod) | remainder; } } memcpy(block, sblock, DPA_BLOCK_SIZE); } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* S_E.c */ #include "include/dpa.h" /* * The substitution table looks like this: * * (s+0)%256 (s+1)%256 (s+2)%256 (s+3)%256 (s+4)%256 (s+5)%256 (s+6)%256 ... * (s+1)%256 (s+2)%256 (s+3)%256 (s+4)%256 (s+5)%256 (s+6)%256 (s+7)%256 ... * (s+2)%256 (s+3)%256 (s+4)%256 (s+5)%256 (s+6)%256 (s+7)%256 (s+8)%256 ... * (s+3)%256 (s+4)%256 (s+5)%256 (s+6)%256 (s+7)%256 (s+8)%256 (s+9)%256 ... * (s+4)%256 (s+5)%256 (s+6)%256 (s+7)%256 ... * (s+5)%256 (s+6)%256 (s+7)%256 (s+8)%256 ... * (s+6)%256 (s+7)%256 (s+8)%256 (s+9)%256 ... * ... */ void S_E(unsigned char *key, unsigned char *block, unsigned int s) { int i; for (i = 0; i < DPA_BLOCK_SIZE; ++i) block[i] = (key[i] + block[i] + s) % 256; return; } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* S_D.c */ #include "include/dpa.h" void S_D(unsigned char *key, unsigned char *block, unsigned int s) { int i; for (i = 0; i < DPA_BLOCK_SIZE; ++i) block[i] = ((256 + block[i]) - key[i] - s) % 256; return; } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* E.c */ #include "include/dpa.h" /* This is the function that is iterated at each round to encrypt */ void E(unsigned char *key, unsigned char *block, unsigned int shift) { rbytechain(block); rbitshift(block, shift); S_E(key, block, shift); } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* D.c */ #include "include/dpa.h" /* This is the function used to decrypt */ void D(unsigned char *key, unsigned char *block, unsigned int shift) { S_D(key, block, shift); lbitshift(block, shift); lbytechain(block); } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* blockchain.c */ #include "include/dpa.h" /* Block chaining for BC modes */ void blockchain(unsigned char *dst, unsigned char *src) { int i; for (i = 0; i < DPA_BLOCK_SIZE; ++i) dst[i] = dst[i] ^ src[i]; return; } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* iv.c */ #include #include #include #include "include/dpa.h" /* Initialization vector */ void IV(unsigned char *block) { int i; srandom(time(NULL) % getpid()); for (i = 0; i < DPA_BLOCK_SIZE; ++i) block[i] = random(); } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* key.c */ #include #include #include #include #include #include #include "include/dpa.h" /* This is the function used to precompute the subkeys */ void DPA_set_key(DPA_KEY *k, unsigned char *key, unsigned int len) { /* Compute subkey #0 */ checksum128(key, k->subkey[0].key, len); /* Compute subkey #1 -> #15: k.n = H(k.(n-1)%16), where 0 <= n <= 15 */ checksum128(k->subkey[0].key, k->subkey[1].key, DPA_KEY_SIZE); checksum128(k->subkey[1].key, k->subkey[2].key, DPA_KEY_SIZE); checksum128(k->subkey[2].key, k->subkey[3].key, DPA_KEY_SIZE); checksum128(k->subkey[3].key, k->subkey[4].key, DPA_KEY_SIZE); checksum128(k->subkey[4].key, k->subkey[5].key, DPA_KEY_SIZE); checksum128(k->subkey[5].key, k->subkey[6].key, DPA_KEY_SIZE); checksum128(k->subkey[6].key, k->subkey[7].key, DPA_KEY_SIZE); checksum128(k->subkey[7].key, k->subkey[8].key, DPA_KEY_SIZE); checksum128(k->subkey[8].key, k->subkey[9].key, DPA_KEY_SIZE); checksum128(k->subkey[9].key, k->subkey[10].key, DPA_KEY_SIZE); checksum128(k->subkey[10].key, k->subkey[11].key, DPA_KEY_SIZE); checksum128(k->subkey[11].key, k->subkey[12].key, DPA_KEY_SIZE); checksum128(k->subkey[12].key, k->subkey[13].key, DPA_KEY_SIZE); checksum128(k->subkey[13].key, k->subkey[14].key, DPA_KEY_SIZE); checksum128(k->subkey[14].key, k->subkey[15].key, DPA_KEY_SIZE); /* Paranoia: overwrite subkey #0 to prevent a possible biais in H * from revealing informations about the initial key. */ checksum128(k->subkey[15].key, k->subkey[0].key, DPA_KEY_SIZE); /* Compute shifts. Shifts are inverted to break a possible relation * between shiftings and subkeys. The last subkey is used to compute * the first shift, and so on... */ k->subkey[0].shift = hash32(k->subkey[15].key, DPA_KEY_SIZE); k->subkey[1].shift = hash32(k->subkey[14].key, DPA_KEY_SIZE); k->subkey[2].shift = hash32(k->subkey[13].key, DPA_KEY_SIZE); k->subkey[3].shift = hash32(k->subkey[12].key, DPA_KEY_SIZE); k->subkey[4].shift = hash32(k->subkey[11].key, DPA_KEY_SIZE); k->subkey[5].shift = hash32(k->subkey[10].key, DPA_KEY_SIZE); k->subkey[6].shift = hash32(k->subkey[9].key, DPA_KEY_SIZE); k->subkey[7].shift = hash32(k->subkey[8].key, DPA_KEY_SIZE); k->subkey[8].shift = hash32(k->subkey[7].key, DPA_KEY_SIZE); k->subkey[9].shift = hash32(k->subkey[6].key, DPA_KEY_SIZE); k->subkey[10].shift = hash32(k->subkey[5].key, DPA_KEY_SIZE); k->subkey[11].shift = hash32(k->subkey[4].key, DPA_KEY_SIZE); k->subkey[12].shift = hash32(k->subkey[3].key, DPA_KEY_SIZE); k->subkey[13].shift = hash32(k->subkey[2].key, DPA_KEY_SIZE); k->subkey[14].shift = hash32(k->subkey[1].key, DPA_KEY_SIZE); k->subkey[15].shift = hash32(k->subkey[0].key, DPA_KEY_SIZE); } /* And this one for using a file as a secret key */ void DPA_set_keyfile(DPA_KEY *k, char *filename) { int fd; void *key; struct stat sb; fd = open(filename, O_RDONLY); if (fd < 0) { fprintf(stderr, "failed to open %s as a secret key.\n", filename); exit(1); } fstat(fd, &sb); key = (unsigned char *)mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0); if (key == (void *)MAP_FAILED) { fprintf(stderr, "mmap() call failure.\n"); exit(1); } DPA_set_key(k, key, sb.st_size); } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* data.c */ /* * Warning: ugliest file ;) */ #include #include #include #include #include #include #include #include #include "include/dpa.h" void DPA_set_data(DPA_DATA *d, unsigned char *data, unsigned int len) { d->data = data; d->length = len; } void DPA_set_datafile(DPA_DATA *d, char *filename) { int fd; struct stat sb; fd = open(filename, O_RDONLY); if (fd < 0) { fprintf(stderr, "failed to open data file %s.\n", filename); exit(1); } fstat(fd, &sb); d->data = (unsigned char *)mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0); if (d->data == (void *)MAP_FAILED) { fprintf(stderr, "mmap() call failure.\n"); exit(1); } d->length = sb.st_size; } /* Allocate enough memory to hold the result of encryption/decryption */ void DPA_set_ciphertext(DPA_DATA *d, DPA_DATA *c, int mode, int action) { int sz; sz = 0; if (action == DPA_ENCRYPT) { if (mode == DPA_MODE_ECB) { if ((d->length % DPA_BLOCK_SIZE) == 0) sz = d->length + DPA_BLOCK_SIZE; else sz = d->length + (DPA_BLOCK_SIZE - (d->length % DPA_BLOCK_SIZE)) + DPA_BLOCK_SIZE; } else if (mode == DPA_MODE_CBC) { if ((d->length % DPA_BLOCK_SIZE) == 0) sz = d->length + (DPA_BLOCK_SIZE * 2); else sz = d->length + (DPA_BLOCK_SIZE - (d->length % DPA_BLOCK_SIZE)) + (DPA_BLOCK_SIZE * 2); } } else if (action == DPA_DECRYPT) { if (mode == DPA_MODE_ECB) sz = d->length - DPA_BLOCK_SIZE; else if (mode == DPA_MODE_CBC) sz = d->length - (DPA_BLOCK_SIZE * 2); } c->data = (unsigned char *)mmap(NULL, sz, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0); if (c->data == (void *)MAP_FAILED) { fprintf(stderr, "mmap() call failure.\n"); exit(1); } c->length = sz; } /* Write the result of encryption/decryption to filename */ void DPA_write_to_file(DPA_DATA *data, char *filename) { int fd; int cnt; int wasfile; wasfile = 0; if (!strcmp(filename, "-")) fd = 1; else { fd = open(filename, O_RDWR|O_CREAT|O_TRUNC, 0600); if (fd < 0) { fprintf(stderr, "failed to open result file %s.\n", filename); exit(1); } wasfile = 1; } for (cnt = 0; cnt < data->length;) if ((data->length - cnt) < DPA_BLOCK_SIZE) cnt += write(fd, data->data + cnt, data->length - cnt); else cnt += write(fd, data->data + cnt, DPA_BLOCK_SIZE); if (wasfile) close(fd); } /* Write the result of checksum to filename in base 16 */ void DPA_sum_write_to_file(DPA_DATA *data, char *filename) { int fd; int cnt; int cnt2; int wasfile; unsigned char base[] = "0123456789abcdef"; unsigned char buffer[DPA_BLOCK_SIZE * 2 + 2]; wasfile = 0; if (!strcmp(filename, "-")) fd = 1; else { fd = open(filename, O_RDWR|O_CREAT|O_TRUNC, 0600); if (fd < 0) { fprintf(stderr, "failed to open result file %s.\n", filename); exit(1); } wasfile = 1; } for (cnt = cnt2 = 0; cnt < DPA_BLOCK_SIZE; ++cnt, (cnt2 += 2)) { buffer[cnt2] = base[*(data->data + data->length - DPA_BLOCK_SIZE + cnt) / 16]; buffer[cnt2 + 1] = base[*(data->data + data->length - DPA_BLOCK_SIZE + cnt) % 16]; } buffer[DPA_BLOCK_SIZE * 2] = '\n'; buffer[DPA_BLOCK_SIZE * 2 + 1] = '\0'; write(fd, buffer, DPA_BLOCK_SIZE * 2 + 2); if (wasfile) close(fd); } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* ecb.c */ /* * Encryption/Decryption in ECB mode. */ #include #include #include #include "include/dpa.h" /* XXX - for better performances, unroll the loops ;) */ void DPA_ecb_encrypt(DPA_KEY *key, DPA_DATA *data, DPA_DATA *cipher) { int j; int cnt; unsigned char *cptr; unsigned char block[DPA_BLOCK_SIZE]; cnt = data->length; cptr = cipher->data; memset(block, 0, 16); for (; cnt > 0; data->data += DPA_BLOCK_SIZE, cptr += DPA_BLOCK_SIZE) { if (cnt < DPA_BLOCK_SIZE) { memcpy(block, data->data, cnt); memset(block + cnt, 0, DPA_BLOCK_SIZE - cnt); } else memcpy(block, data->data, DPA_BLOCK_SIZE); for (j = 0; j < 16; ++j) E(key->subkey[j].key, block, key->subkey[j].shift); memcpy(cptr, block, DPA_BLOCK_SIZE); cnt -= DPA_BLOCK_SIZE; } /* Padding block */ memset(block, 0, DPA_BLOCK_SIZE); if (data->length % DPA_BLOCK_SIZE) block[DPA_BLOCK_SIZE - 1] = DPA_BLOCK_SIZE - data->length % DPA_BLOCK_SIZE; for (j = 0; j < 16; ++j) E(key->subkey[j].key, block, key->subkey[j].shift); memcpy(cptr, block, DPA_BLOCK_SIZE); } void DPA_ecb_decrypt(DPA_KEY *key, DPA_DATA *data, DPA_DATA *cipher) { int j; int cnt; unsigned char padding; unsigned char *cptr; unsigned char block[DPA_BLOCK_SIZE]; /* Data is padded so... we got at least 2 * DPA_BLOCK_SIZE bytes and * data->length / DPA_BLOCK_SIZE should be even */ if ((data->length % DPA_BLOCK_SIZE) || data->length < (2 * DPA_BLOCK_SIZE)) exit(1); /* Extract padding information */ memcpy(block, data->data + data->length - DPA_BLOCK_SIZE, DPA_BLOCK_SIZE); for (j = 15; j >= 0; --j) D(key->subkey[j].key, block, key->subkey[j].shift); padding = block[DPA_BLOCK_SIZE - 1]; cipher->length -= padding; cptr = cipher->data; cnt = data->length - DPA_BLOCK_SIZE; memset(block, 0, DPA_BLOCK_SIZE); for (; cnt > 0; cnt -= DPA_BLOCK_SIZE, data->data += DPA_BLOCK_SIZE, cptr += DPA_BLOCK_SIZE) { memcpy(block, data->data, DPA_BLOCK_SIZE); for (j = 15; j >= 0; --j) D(key->subkey[j].key, block, key->subkey[j].shift); if (cnt >= DPA_BLOCK_SIZE) memcpy(cptr, block, DPA_BLOCK_SIZE); else memcpy(cptr, block, DPA_BLOCK_SIZE - (padding % DPA_BLOCK_SIZE)); } } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* cbc.c */ /* * Encryption/Decryption in CBC mode. */ #include #include #include #include "include/dpa.h" /* XXX - for better performances, unroll the loops ;) */ void DPA_cbc_encrypt(DPA_KEY *key, DPA_DATA *data, DPA_DATA *cipher) { int j; int cnt; unsigned char *cptr; unsigned char block[DPA_BLOCK_SIZE]; unsigned char iv[DPA_BLOCK_SIZE]; unsigned char xblock[DPA_BLOCK_SIZE]; /* IV */ cptr = cipher->data; IV(iv); memcpy(xblock, iv, DPA_BLOCK_SIZE); for (j = 0; j < 16; ++j) E(key->subkey[j].key, iv, key->subkey[j].shift); memcpy(cptr, iv, DPA_BLOCK_SIZE); cptr += DPA_BLOCK_SIZE; cnt = data->length; memset(block, 0, 16); for (; cnt > 0; data->data += DPA_BLOCK_SIZE, cptr += DPA_BLOCK_SIZE) { if (cnt < DPA_BLOCK_SIZE) { memcpy(block, data->data, cnt); memset(block + cnt, 0, DPA_BLOCK_SIZE - cnt); } else memcpy(block, data->data, DPA_BLOCK_SIZE); blockchain(block, xblock); for (j = 0; j < 16; ++j) E(key->subkey[j].key, block, key->subkey[j].shift); memcpy(xblock, block, DPA_BLOCK_SIZE); memcpy(cptr, block, DPA_BLOCK_SIZE); cnt -= DPA_BLOCK_SIZE; } /* Padding */ memset(block, 0, DPA_BLOCK_SIZE); if (data->length % DPA_BLOCK_SIZE) block[DPA_BLOCK_SIZE - 1] = DPA_BLOCK_SIZE - data->length % DPA_BLOCK_SIZE; blockchain(block, xblock); for (j = 0; j < 16; ++j) E(key->subkey[j].key, block, key->subkey[j].shift); memcpy(cptr, block, DPA_BLOCK_SIZE); } void DPA_cbc_decrypt(DPA_KEY *key, DPA_DATA *data, DPA_DATA *cipher) { int j; int cnt; unsigned char padding; unsigned char *cptr; unsigned char block[DPA_BLOCK_SIZE]; unsigned char xblock[DPA_BLOCK_SIZE]; unsigned char xblockprev[DPA_BLOCK_SIZE]; unsigned char *xorptr; /* * CBC mode uses padding, data->length / DPA_BLOCK_SIZE _MUST_ be even. * Also, we got a block for the IV, at least a block for the data and * a block for the padding information, this makes the size of cryptogram * at least 3 * DPA_BLOCK_SIZE. */ if ((data->length % DPA_BLOCK_SIZE) || data->length < (3 * DPA_BLOCK_SIZE)) exit(1); /* Extract padding information by undoing block chaining on last block */ memcpy(block, data->data + data->length - DPA_BLOCK_SIZE, DPA_BLOCK_SIZE); for (j = 15; j >= 0; --j) D(key->subkey[j].key, block, key->subkey[j].shift); xorptr = data->data + data->length - (DPA_BLOCK_SIZE * 2); blockchain(block, xorptr); padding = block[DPA_BLOCK_SIZE - 1]; cipher->length -= padding; /* Extract Initialization vector */ memcpy(xblock, data->data, DPA_BLOCK_SIZE); for (j = 15; j >= 0; --j) D(key->subkey[j].key, xblock, key->subkey[j].shift); cptr = cipher->data; cnt = data->length - (DPA_BLOCK_SIZE * 2); memset(block, 0, DPA_BLOCK_SIZE); for (data->data += DPA_BLOCK_SIZE; cnt >= DPA_BLOCK_SIZE; cnt -= DPA_BLOCK_SIZE, data->data += DPA_BLOCK_SIZE, cptr += DPA_BLOCK_SIZE) { memcpy(block, data->data, DPA_BLOCK_SIZE); memcpy(xblockprev, block, DPA_BLOCK_SIZE); for (j = 15; j >= 0; --j) D(key->subkey[j].key, block, key->subkey[j].shift); blockchain(block, xblock); if (cnt >= DPA_BLOCK_SIZE) memcpy(cptr, block, DPA_BLOCK_SIZE); else memcpy(cptr, block, DPA_BLOCK_SIZE - (padding % DPA_BLOCK_SIZE)); memcpy(xblock, xblockprev, DPA_BLOCK_SIZE); } } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* sum.c */ /* NEEDS_FIX */ /* * This is basically a CBC encryption with a fixed IV and fixed key, the * last block being the checksum. This needs a rewrite because there is * no need to allocate memory for the whole ciphertext as only two blocks * are needed. */ #include #include #include #include "include/dpa.h" /* XXX - for better performances, unroll the loops ;) */ void DPA_sum(DPA_KEY *key, DPA_DATA *data, DPA_DATA *cipher) { int j; int cnt; unsigned char *cptr; unsigned char block[DPA_BLOCK_SIZE]; unsigned char iv[DPA_BLOCK_SIZE]; unsigned char xblock[DPA_BLOCK_SIZE]; /* Fixed key */ DPA_set_key(key, (unsigned char *)"deadbeef", 8); /* Fixed IV */ memcpy(iv, "0123456789abcdef", DPA_BLOCK_SIZE); memcpy(xblock, iv, DPA_BLOCK_SIZE); cptr = cipher->data; memcpy(xblock, iv, DPA_BLOCK_SIZE); for (j = 0; j < 16; ++j) E(key->subkey[j].key, iv, key->subkey[j].shift); memcpy(cptr, iv, DPA_BLOCK_SIZE); cptr += DPA_BLOCK_SIZE; cnt = data->length; memset(block, 0, 16); for (; cnt > 0; data->data += DPA_BLOCK_SIZE, cptr += DPA_BLOCK_SIZE) { if (cnt < DPA_BLOCK_SIZE) { memcpy(block, data->data, cnt); memset(block + cnt, 0, DPA_BLOCK_SIZE - cnt); } else memcpy(block, data->data, DPA_BLOCK_SIZE); blockchain(block, xblock); for (j = 0; j < 16; ++j) E(key->subkey[j].key, block, key->subkey[j].shift); memcpy(xblock, block, DPA_BLOCK_SIZE); memcpy(cptr, block, DPA_BLOCK_SIZE); cnt -= DPA_BLOCK_SIZE; } memset(block, 0, DPA_BLOCK_SIZE); if (data->length % DPA_BLOCK_SIZE) block[DPA_BLOCK_SIZE - 1] = DPA_BLOCK_SIZE - data->length % DPA_BLOCK_SIZE; blockchain(block, xblock); for (j = 0; j < 16; ++j) E(key->subkey[j].key, block, key->subkey[j].shift); memcpy(cptr, block, DPA_BLOCK_SIZE); } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* usage.c */ #include #include #include #include void usage(void) { fprintf(stderr, "usage: dpa -a action -m mode -k key -d data -o outfile\n"); fprintf(stderr, " dpa -s filename\n"); fprintf(stderr, "\taction can be : encrypt, decrypt\n"); fprintf(stderr, "\tmode can be : ecb, cbc\n"); fprintf(stderr, "\tkey can be : \"key\" or file:/path/to/keyfile\n"); fprintf(stderr, "\tdata can be : \"data\" or file:/path/to/datafile\n"); fprintf(stderr, "\toutfile can be: \"-\" (stdout) or a filename\n"); fprintf(stderr, "\twhen -s is used, a checksum of filename is computed\n"); exit (EX_USAGE); } 8<- - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - 8< - - - - - /* main.c */ #include #include #include #include #include "include/dpa.h" int main(int argc, char *argv[]) { int kflag; int dflag; int sflag; int mflag; int aflag; int oflag; int opt; int mode; int action; char *output; DPA_KEY key; DPA_DATA data; DPA_DATA cipher; mode = DPA_MODE_ECB; action = DPA_ENCRYPT; output = "-"; mflag = aflag = kflag = dflag = sflag = oflag = 0; while ((opt = getopt(argc, argv, "a:m:k:d:o:s:")) != -1) { switch (opt) { case 'a': if (!strcmp(optarg, "enc") || !strcmp(optarg, "encrypt")) action = DPA_ENCRYPT; else if (!strcmp(optarg, "dec") || !strcmp(optarg, "decrypt")) action = DPA_DECRYPT; else { fprintf(stderr, "unknown action, expected encrypt or decrypt\n"); return (EX_USAGE); } aflag = 1; break; case 'm': if (!strcmp(optarg, "ecb")) mode = DPA_MODE_ECB; else if (!strcmp(optarg, "cbc")) mode = DPA_MODE_CBC; else { fprintf(stderr, "unknown mode, expected ecb or cbc\n"); return (EX_USAGE); } mflag = 1; break; case 'k': if (strncmp(optarg, "file:", 5) || strlen(optarg) == 5) DPA_set_key(&key, (unsigned char *)optarg, strlen(optarg)); else DPA_set_keyfile(&key, optarg + 5); kflag = 1; break; case 'd': if (strncmp(optarg, "file:", 5) || strlen(optarg) == 5) DPA_set_data(&data, (unsigned char *)optarg, strlen(optarg)); else DPA_set_datafile(&data, optarg + 5); dflag = 1; break; case 'o': output = optarg; oflag = 1; break; case 's': DPA_set_datafile(&data, optarg); sflag = 1; break; default: usage(); } } if ((!aflag || !mflag || !kflag || !dflag) && !sflag) usage(); if (sflag) { DPA_set_ciphertext(&data, &cipher, DPA_MODE_CBC, DPA_ENCRYPT); DPA_sum(&key, &data, &cipher); DPA_sum_write_to_file(&cipher, output); } else { DPA_set_ciphertext(&data, &cipher, mode, action); if (action == DPA_ENCRYPT) { if (mode == DPA_MODE_ECB) DPA_ecb_encrypt(&key, &data, &cipher); else if (mode == DPA_MODE_CBC) DPA_cbc_encrypt(&key, &data, &cipher); } else if (action == DPA_DECRYPT) { if (mode == DPA_MODE_ECB) DPA_ecb_decrypt(&key, &data, &cipher); else if (mode == DPA_MODE_CBC) DPA_cbc_decrypt(&key, &data, &cipher); } DPA_write_to_file(&cipher, output); } return (EX_OK); } |=[ EOF ]=---------------------------------------------------------------=|