Copy Link
Add to Bookmark
Report
Phrack Inc. Volume 11 Issue 62 File 14
==Phrack Inc.==
Volume 0x0b, Issue 0x3e, Phile #0x0e of 0x10
|=---------=[ A Dynamic Polyalphabetic Substitution Cipher ]=------------=|
|=-----------------------------------------------------------------------=|
|=----------------=[ Veins <veins at tristeza.org> ]=--------------------=|
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 <veins at tristeza.org>
*
* 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 <sys/stat.h>
#include <sys/mman.h>
#include <fcntl.h>
#include <sysexits.h>
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 <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sysexits.h>
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 <string.h>
#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 <stdlib.h>
#include <time.h>
#include <unistd.h>
#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 <sys/types.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#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 <sys/types.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#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 <stdio.h>
#include <string.h>
#include <unistd.h>
#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 <stdio.h>
#include <string.h>
#include <unistd.h>
#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 <stdio.h>
#include <string.h>
#include <unistd.h>
#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 <stdio.h>
#include <stdlib.h>
#include <sysexits.h>
#include <unistd.h>
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 <stdio.h>
#include <string.h>
#include <sysexits.h>
#include <unistd.h>
#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 ]=---------------------------------------------------------------=|
