OTP4U algorithm

This paper contains 3 paragraphs:
1. Introduction
2. Considerations about the security of OTP4U
3. Pseudo-code algorithm (with figures)
3.1. Changes in the 0.8.2 release
3.2. Known-plaintext attack


1. Introduction

OTP4U (One Time Pad for you) is a new crypto-system which provides an easy to use cipher, very similar to the One Time Pad, which is the only known unbreakable cipher. If OTP4U probably is not unbreakable, it seems that the only attack against it is a brute force attack. A known-plaintext attack, as explained below, should be infeasible. The Java open source implementation provided in my site is a demonstration of OTP4U and is also the best description for the algorithm for anyone that knows the Java language. For everyone else, below I have provided many pseudo-code lines, and I hope this will help understanding the algorithm.
The idea of OTP4U is similar to that of Sysepub, which inspired OTP4U and from which it has been partly derived.
Like a One Time Pad (OTP), OTP4U uses a key made of truly random bytes, that are used to generate an array to which the plaintext is XORed to obtain the ciphertext. The great limitation of the OTP is that "Alice and Bob" have to share the key between them; the key must be of the same length of the plaintext, so a secure channel is needed to exchange the key.
The main goal of OTP4U is to make the key exchange simpler. Thus, instead of using a secure channel to exchange a large amount of random bytes when needed, Alice and Bob will need a secure channel only the first time, when they start the process. They will need to share only a little random byte array (say of very few K-Bytes); let's call this array K4K0 (Key for Key 0, as it will be used to transmit securely another key).
Alice and Bob share K4K0
Once that K4K0 has been shared, let's see how Alice and Bob proceed.
Supposing that Alice has got a truly Random Number Generator RNG (used also to generate K4K0), she generates the bytes that will be used as the OTP-key (K4M1, Key for Message 1) and she generates also another byte array (p0, called "public" key, in the sense that is not secret) that she will send, on an insecure channel, to Bob. And only Bob will be able to obtain K4M1 from p0, because to do this the only way is using K4K0, that is secret.
The Java class used to manage the key "enciphering/deciphering" is called
KeyManager. It's an abstract class, so it allows multiple subclasses to implement it. The OTP4U main class is designed to be able to dinamically instantiate a particular key manager at runtime, with the aim of simplifying and encouraging the writing of new key managers. This release includes two different impementations of KeyManager: KM_Permutation and KM_Xor.
The first obtains K4M1 and K4K1 from the "public" key p0, with a permutation of its bytes. This permutation is quite random, and an adversary could not obtain it, as it is determined from the byte values of the "public" key itself and of K4K0 (secret)(detailed pseudo-code description below).
The second implementation instead uses K4Kn to generate a new array that is XORed to the random stream r0 to "encipher" it and generate the "public" key p0. This second method seems as secure as the first, but it's less performing, as it requires that the length of the encrypted (public) key is at least two times the length of the plaintext. In certain cases this would be a problem, but in many cases this is not.
Alice generates exactly l random bytes (where l = 2*K4K0.length) in the array r0 with the RNG. Now she enciphers r0 using K4K0 as key and obtaining p0 (detailed pseudo-code description below).
Now Alice sends to Bob on an insecure channel p0, from which he is able to recover r0.
Finally Alice and Bob split r0 in two arrays: the right end (K4K1) and the left end, that will be used to generate K4M1. K4K1 will be used in the next iteration of the process to exchange r1, and K4M1 contains the truly random bytes that will be used as key for the OTP-like encryption of their plaintexts (i.e.: ciphertext = plaintext XOR K4M1).
Getting the ciphertext
There are many possible ways for exchanging K4K0: I suggest the use of a Criptographically Secure Pseudo-Random Number Generator (CSPRNG) to encipher K4K0, or other existing systems that can be useful for a key exchange (like those in public key schemes); the present implementation of OTP4U assumes that the users start with K4K0 already shared.
Finally, there is also an OTP4U variant (not yet implemented) based upon the use of a CSPRNG to encipher the random bytes of r0; in this way Alice and Bob can use all the bytes of r0 (not only the half of the array, like KM_Xor), however the security of this variant depends on the level of security of the CSPRNG. Again, the pseudo-code description can be found below.

2. Considerations about the security of OTP4U

The use of a RNG (instead of a PRNG) makes the OTP unbreakable: the ciphertext could be obtained from any plaintext with the same probability, thus it gives absolutely no information about the real plaintext.
Now, let's see the information that an adversary C of Alice and Bob can get, and what he could obtain from it.
The first array that C could get is p0: this should appear to him absolutely random, in any case.
In the KM_Permutation variant, he knows that with a permutation of its bytes he could obtain K4M1 concatenated with K4K1. But the number N(n) of permutations of an array of length n is a very large number: if there were n distinct objects this number would be n! , but normally a byte array has every possible byte value repeated several times, so N(n) is smaller (because some permutations act on identical byte values, so they are equivalent and they have to be excluded from the count), anyway too large even for the fastest computer. To have an idea of the dimension of N(n), consider the asymptotical function:
f(n) = n! / ((n/256)!)^256
f(n) counts the number of permutations of a byte array of length n (multiple of 256), in which the 256 possible byte values have an uniform distribution (every value occurs exactly n/256 times). The denominator counts the permutations to be discarded. Some examples: f(512) has 1089 digits, f(1024) has 2286 digits, etc..
f(n) is "asymptotical" to N(n) because a randomly generated byte array tends to have an uniform distrubution of its bytes, so f(n) can be taken as a good approximation of N(n).
Also a brute force attack on K4K0 is infeasible if K4K0 is long enough: a length of only 1 KB implies a keyspace of 256^1024 = 2^8192, a number of 2466 digits!
About the KM_XOR variant: here p0 comes from the XOR between r0 and concat(K4K0, A(K4K0, r0Left) (see below)). In fact, r0 is the "purest" random array, as the second term of the XOR could show some little organization inside; but, having only p0, there's no way to obtain the two terms of this XOR.
Another array that C could get is for example: ciphertext1 = plaintext1 XOR K4M1
In the KM_Permutation variant K4M1 comes from a random permutation of the truly random array p0, and in the KM_Xor variant K4M1 is permutation(K4K0, r0Right) (see below). Hence if a RNG was used, K4M1 still looks really random and the security of plaintext1 is absolute: a ciphertext-only attack is infeasible under this assumption.
Finally, C could try a known-plaintext attack: the discussion of this case requires some pseudo-code explantions, which can be found at the end of this paper.


I guess the following notations are obvious:
byte[] is a byte array; x.length is the length of the byte[] x
XOR between two byte array (of the same length) is equivalent to XORing byte per byte from the first to the last byte.
A byte value can be considered also as an integer from -128 to 127.
% is the modulo: a%n is the same of a mod n; for simplicity I assume that always is: a mod n >= 0
= is assignation, not equality

3. Pseudo-Code Algorithms


Here are presented the algorithms of two key managers, provided within OTP4U. Anyway, I think some improvements still can be done. New proposals, or new implementations of KeyManager, are welcome (after all, contributions are fundamental in open source projects). Let's start with the key manager based on the permutation.


KM_Permutation

OTP4U Process (First iteration)

1. Alice and Bob share K4K0

2. Alice gets l truly random bytes from her random numbers generator: p0 = RNG(l)

3. Alice sends to Bob p0

4. Alice gets K4M1, K4K1 from permutation(p0, K4K0)
5. Bob gets K4M1, K4K1 from permutation(p0, K4K0)

Now Alice and Bob can use the bytes of K4M1 as a key for a One Time Pad.
These bytes should never be reused. So, when new random bytes are needed
Alice gets p1 = RNG(l) and the same process is iterated (from 2 to 5)

OTP4U Process (nth iteration)

2. Alice gets l truly random bytes from her random numbers generator: pn = RNG(l)

3. Alice sends to Bob pn

4. Alice gets K4Mn+1, K4Kn+1 from permutation(pn, K4Kn)
5. Bob gets K4Mn+1, K4Kn+1 from permutation(pn, K4Kn)


- Key Permutator

permutation(p0, K4K0)

INPUT: The byte[] p0, K4K0
OUTPUT: The byte[] K4M1, K4K1

Variables: integers kLen = K4K0.length, pLen = p0.length, b = 0, v = 0, n, tot = pLen - kLen, c

1. for n = 0 to tot do:
   1.1 c = 128 + p0[b%pLen] + (128 + k[b%kLen]) * 256 + (128 + p0[(b + 1)%pLen]) * 65536 +
      + (128 + k[(b + 1)%kLen]) * 123456
   1.2 v = 128 + p0[c%pLen] + (128 + k[c%kLen]) * 256 + (128 + p0[(c + 1)%pLen]) * 65536 +
      + (128 + k[(c + 1)%kLen]) * 123456
   1.3 b = (b + v) % pLen
   1.4 K4M1[n] = p0[b];
   1.5 pLen = pLen-1
   1.6 p0[b] = p0[pLen];
2. K4K1 = {p0[0], p0[1], .. , p[kLen - 2], p[kLen - 1]}
3. return K4M1, K4K1

This algorithm can be explained in few words: the permutation is done copying byte by byte from p0 to K4M1 in a loop. b is the index in p0 of the byte that is copied into K4M1 in the nth step of the loop. The next step, the value of b is obtained in function of 4 byte values of p0, 4 byte values of K4K0, and the previous value of b itself (points 1.1-1.3). This is done until K4M1 has pLen-kLen bytes, and K4K1 is assigned from the remaining bytes in p0 (from index 0 to kLen-1).
Being p0 and K4K0 randomly generated, in every step, b can assume every possible value with quite the same probability.
Dimensions recommended for the keys: K4K0 of 1-2 KB, p0 of 20 KB or more.

KM_Xor

Functions: A(x,y): Taken the byte arrays x,y returns the byte array A(x,y),
of the same length of x and y.
concat(a,b): Taken the byte[] a,b returns the concatenation of a and b.
left(x), right(x): Return the left and rigth end of x (i.e. the first n/2 bytes and the last n/2 bytes, where n = x.length)

- Key Encryption

getEncipheredKey ( K4K0, r0 )

INPUT: The byte arrays K4K0 (shared), r0 (r0.length = 2 * K4K0.length).
OUTPUT: The byte array p0.

Variables: byte[] temp


1. temp = concat(K4K0, A(K4K0, left(r0)))
2. p0 = r0 XOR temp
3. return p0
The key encryption

- Key Decryption

getKey ( K4K0, p0 )

INPUT: byte[] p0, K4K0 (shared)
OUTPUT: byte[] r0

Variables: byte[] temp, r0Left, r0Right


1. r0Left = left(p0) XOR K4K0
2. temp = A(r0Left, K4K0)
3. r0Right = right(p0) XOR temp
4. r0 = concat(r0Left, r0Right)
5. return r0
The key decryption


- Iteration

iterate(r0, K4K0)

INPUT: byte[] r0, K4K0
OUTPUT: byte[] K4M1, K4K1


1. K4M1 = permutationXor(K4K0, right(r0))
2. K4K1 = left(r0)
3. return K4M1, K4K1

Where the function permutationXor is defined below (section 3.1)

OTP4U Process (First iteration)

1. Alice and Bob share K4K0

2. Alice gets l truly random bytes from her random numbers generator: r0 = RNG(l)
   Alice computes p0 = getEncipheredKey( K4K0, r0 )
   Alice gets K4M1, K4K1 from iterate(r0)

3. Alice sends to Bob p0

4. Bob computes r0 = getKey ( K4K0, p0)
   Bob gets K4M1, K4K1 from iterate(r0)

Now Alice and Bob can use the l/2 bytes of K4M1 as a key for a One Time Pad.
These bytes should never be reused. So, when new random bytes are needed
Alice gets r1 = RNG(l) and the same process is iterated (from 2 to 4)

OTP4U Process (nth iteration)

2. Alice gets l truly random bytes from her generator: rn = RNG(l)
   Alice computes pn = getEncipheredKey( K4Kn, rn )
   Alice gets K4Mn+1, K4Kn+1 from iterate(rn)

3. Alice sends to Bob pn

4. Bob computes rn = getKey ( K4Kn, pn)
   Bob gets K4Mn+1, K4Kn+1 from iterate(rn)



OTP4U CSPRNG Variant (First iteration)

1. Alice and Bob share s (the seed of the CSPRNG)

2. Alice gets l truly random bytes from her random numbers generator: r0 = RNG(l) (or from the CSPRNG: but this could offer more data to the cryptanalyst)
   Alice gets l pseudo-random bytes from her CSPRNG: k0 = CSPRNG(s,l)
   Alice computes p0 = k0 XOR r0
   Alice gets K4M1 from permutationXor(k0, r0)

3. Alice sends to Bob p0

4. Bob gets l pseudo-random bytes from his CSPRNG: k0 = CSPRNG(s,l)
   Bob computes r0 = k0 XOR p0
   Bob gets K4M1 = permutationXor(k0, r0)

Where the function permutationXor is defined below (section 3.1)

Now Alice and Bob can use the l bytes of K4M1 as a key for a One Time Pad.
These bytes should never be reused. So, when new random bytes are needed
Alice gets r1 = RNG(l), k1=CSPRNG(s,l) and the same process is iterated (from 2 to 4)

3.1 Changes in the 0.8.2 release

Since release 0.8.2, a new way was introduced to improve security in the key exchange. In the newsgroup sci.crypt, during a discussion about OTP4U, John Savard pointed out a possible weakness in the key exchange system: an attacker, knowing encrypted messages n+1 and n+2 in conjunction with P(n) and P(n+1) could try to obtain some informations about K4Kn.
But why Alice and Bob have to give these information (P(n)) to the attacker? It suffices that Alice appends the 2 files (P(0) and ciphertext1, with P(0).length>ciphertext1.length) in a single file (let's call it Mixed(1)) and, while Bob is still able to recover P(0) and ciphertext1 (he knows K4K0 length), the attacker doesn't know anymore P(0) and so he can't perform the analysis described by Savard. Anytime a new key exchange is needed, Alice generates a new Mixed(n) and sends it to Bob. The attacker after many key exchanges can still estimate the K4K0 length, so Alice and Bob should after a period of time change its length.
A future version will provide a mixing function more complex than the append (depending on K4Kn).

Algorithm (Mixed mode. c0 .. cn are the ciphertexts of the nth iteration):
OTP4U Process (First iteration)

1. Alice and Bob share K4K0

2. Alice gets l truly random bytes from her random numbers generator: r0 = RNG(l)
   Alice computes p0 = getEncipheredKey( K4K0, r0 )
   Alice computes m0 = mix(p0, c0)    Alice gets K4M1, K4K1 from iterate(r0)

3. Alice sends to Bob m0

4. Bob computes p0 and c0 from m0
   Bob computes r0 = getKey ( K4K0, p0)
   Bob gets K4M1, K4K1 from iterate(r0)

Now Alice and Bob can use the l/2 bytes of K4M1 as a key for a One Time Pad.
These bytes should never be reused. So, when new random bytes are needed
Alice gets r1 = RNG(l) and the same process is iterated (from 2 to 4)

OTP4U Process (nth iteration)

2. Alice gets l truly random bytes from her generator: rn = RNG(l)
   Alice computes pn = getEncipheredKey( K4Kn, rn )
   Alice computes mn = mix(pn, cn)    Alice gets K4Mn+1, K4Kn+1 from iterate(rn)

3. Alice sends to Bob mn

4. Bob computes pn and cn from mn
   Bob computes rn = getKey ( K4Kn, pn)
   Bob gets K4Mn+1, K4Kn+1 from iterate(rn)

3.2 Known-plaintext attack

This paragraph was written for version 0.8.0. With the mixed mode, the attacker has an even more difficult work to do.
An adversary C could try a known-plaintext attack. For example, if C gets the whole plaintext of the nth iteration, he gets also K4Mn with a single XOR. Let's see in the two cases what he could do.

KM_Permutation

Having K4Mn, with a comparison C can obtain the exact distribution of byte values of K4Kn. But he doesn't know the sequence in which they are placed in K4Kn, and as usual, there are nearly kLen! / ((kLen/256)!)^256 possible permutations (see paragraph 2) that assign this sequence.
Trying to obtain more informations from the permutation(pn, K4Kn) algorithm seems also very difficult: in every step of the loop there are multiple values of the K4Kn bytes that can produce the same result.

KM_Xor

If he could obtain, from K4Mn, RnRight C would also get, with a XOR, A(K4Kn, RnLeft); the sysyem is secure if C can't get RnRight from K4Mn; and it's two times secure if C can't get K4Kn and RnLeft; i.e., knowing z=A(x,y) he can't obtain x and y (knowing K4Kn would lead to K4Kn+1, so C would break the system as he could compute all former and future iterations).
Hence the security of the system is deeply connected to the nature of the permutationXor(e,r) and A(x,y) functions:
a necessary condition is that permutationXor(e,r) gives as little information as possibile about e and r; and the knowledge of A(x,y) gives as little information as possibile about x and y.
OTP4U uses a permutationXor function with this level of uncertainty: knowing the array permutationXor(e,r) and using nBlock blocks, there are nBlock! possible candidates to be a preimage of permutationXor(e,r). I think that 32 or 64 are two good values for nBlock, giving 32! and 64! . The length of left(r0) must be a multiple of nBlock.
About the A function (which corresponds to the "autoKey" method in the OTP4U class) : knowing the array A(x,y) of length aLength, there are 2^(4*aLength) possible candidates to be a preimage of A(x,y). For example, even an array of only 1 KB (1024 Bytes) would have at least 2^4096 possible preimages; but a reasonable dimension of K4Kn and K4Mn is certainly to be considered of 10 KB or more, thus assuring that this known-plaintext attack would be computationally infeasible.

Now here's these two algorithms (it's possible these are not the best algorithms for this purpose; if there will be better candidates I'll substitute them as soon as possible):

permutationXor(e, r)

Functions: sort(x) returns the array x sorted
indexOf(b, x) returns the index (as integer) of the byte b within the array x

INPUT: byte[] e,r , integer nBlock
OUTPUT: byte[] z

Variables: byte[] sorted,noDuplicate (of nBlock bytes)
integer[] perm

1. Assign the noDuplicate array values with the first bytes in e, discarding the
   duplicates, until nBlock bytes are assigned.
2. sorted = sort(noDuplicate)
3. for i=0 to nBlock - 1
   3.1 perm[i] = indexOf(noDuplicate[i], sorted)
4. Now the perm array represents a permutation, by which the blocks (br[i]) in r of length r.length/nBlock
   are shuffled to generate the array z (with the blocks zr[i]):
   zr[i] = br[perm[i]]
5. return z

Example: Let nBlock=8, perm = {5, 2, 6, 3, 1, 0, 7, 4}.
The figure graphically shows this permutation.
How the perm array shuffles the r blocks

A(x,y)

INPUT: byte[] x,y , integer len=x.length=y.length
OUTPUT: byte[] z

Variables: byte[] temp


1. for i=0 to len-1 do:
   1.1 temp[i] = y[n-1-i]
2. z = x XOR temp
3. return z


Let's see what a cryptanalist C has to do when he tries to obtain (K4K0,left(r0)) from A(K4K0,left(r0)). The number of possible preimages (x) of A(x) is computed as follows.
Let's suppose that C knows left(p0), as it was transmitted on an insecure channel. He could now perform these steps:
As left(p0) = left(r0) XOR K4K0
and A(K4K0,left(r0)) = K4K0 XOR temp
where temp was obtained from left(r0) as described in the A algorithm;
symmetric = left(p0) XOR A(K4K0,left(r0)) = left(r0) XOR K4K0 XOR K4K0 XOR temp =
= left(r0) XOR temp
The array symmetric gives this level of information about r0: assigning the byte values from r0[0] to r0[len/2-1] (the left(left(r0)) array), implies fixing the remaining byte values, in order to obtain the array symmetric; thus is determined left(r0).
The first bytes are len/2, and the can assume 256 values independently. But len/2=aLength, so:
256^(len/2)=(2^8)^(aLength/2)=2^(4*aLength).


Example: consider two byte[] A(x,y), left(p0) of 8 bytes (I use an integer between -128 and 127 to represent a byte):

left(p0) = {1, 3, 1, 7, 1, 3, 1, 15}
A(x,y) = {8, 6, 4, 6, 0, 6, 4, 6}.
aLength = 8

This could have been obtained, for example, from the byte[] x,y:

x = {0, 1, 2, 3, 4, 5, 6, 7}
y = {1, 2, 3, 4, 5, 6, 7, 8}

in the following way.

temp = {8, 7, 6, 5, 4, 3, 2, 1}
x XOR temp=
A(x,y) = {8, 6, 4, 6, 0, 6, 4, 6}

Now, let's compute symmetric:
symmetric = left(p0) XOR A(x,y) = {9, 5, 5, 1, 1, 5, 5, 9} =
= y XOR temp
Instead of y, also y' = {0, 2, 3, 4, 5, 6, 7, 9} (the first and last byte have changed their values) will produce the same array symmetric; from y' I find x':
x' = {8, 6, 4, 6, 0, 6, 4, 6} XOR temp' = {1, 1, 2, 3, 4, 5, 6, 6}.
The equation (1) x' XOR y' = left(p0) is still verified.
In conclusion I can assign the first 4 bytes with any possible value; the last 4 bytes are assigned consequently; as I assign a y', it always exists a x' that verifies the equation (1). So the number of possible preimages of A(x,y) is:
256^4 = 2^32 = 2^(4*8) = 2^(4*aLength)


NOTE: The pseudo-code algorithms presented here aren't the exact transposition of the Java code; they are rather intended to make the idea of OTP4U more easy to assimilate. Nevertheless, I tried to mantain a quite strict correspondence where possible.




Teutoburgo Home      OTP4U index      Download OTP4U for free!



Copyright Pierre Blanc 2003
Last modified: Jul 28 15:26:40 CET 2003
Bookmark and Share