One Time Pad Alphabet Size

Question

I am building a simple one time pad system using a low-power microcontroller to XOR a stored key with an input string, and vice versa. Due to several internal factors, it's very preferable for the system to use only the 95 "printable ascii" chars instead of full 256-values bytes to represent pad keys. Since the input is restricted to simple plain-ascii as well, that should be enough coverage if I understand the OTP process correctly.

My pad-making question is about converting random 0-255 values to plain-ascii chars, representing 0-94 or so. Would it be more secure to convert each 0-255 value (x) using:

1. x % 95 (x mod 95) to get all the possible chars, but with the 65-94 values being 50% more likely than 0-64 values.

2. int(x / 3), to get a uniform distro of keys chars from 0-84 value, where each value has odds of 3/255 (~1/85) of being used.

While #1 has 10 more key possibilities, #2 has uniform distribution, and I can input from an 85 "letter" alphabet if needed (instead of 95).

Given a random 0-255 input, which down-conversion likely results in better security?

edit: fixed the unclear range "0-85" and "0-95" to reflect 85 and 95 possibilities.

Answer 1

Neither of the options is any good; both your random number schemes are biased.

If you use modular addition, which seems a good idea for your one time pad, then your lower characters will never be encrypted to the highest possible characters for the scheme where you use [0-85) distribution. That's pretty damning and such a scheme would be considered broken immediately.

For the other solution, just dividing by 3, the problem you're facing is statistics. Say you expect a certain low value at a certain location then you can basically check if your value has a preference for low value + biased ouput (i.e. not reaching a higher value often enough). In that case you can be reasonably certain that this value is correct. It isn't as bad as 0..85, but it is still pretty bad.

---

What you can do is to generate a number of bits $x$ larger than $2^x \gt 95$ so that $2^x \bmod 95$ results in a small number. Then calculate the $y$ so that $y = \lfloor 2^x / 95 \rfloor$. Finally, calculate a maximum $m$ so that $m = y \cdot 95$.

Now when generating a number in the range [0-95) you can:

1. generate a value $c$ in the range [0-$2^x$) by simply generating $x$ bits and converting it to a number;
2. check if $c \geq m$, if this is the case, restart;
3. return $c / y$.

In this case you'd have $2^{12}$ : rest 11 out of 4096 after division. So if you generate 12 bits the chance that you have to regenerate is tiny. You'd of course still be spilling bits, some 5 bits per character, but your output is unbiased and your running time is very close to deterministic (i.e. the chance that you need to repeat the procedure and generate another number for a character is very low).

---

Note that this answer is based on the precondition that the range must be [0-95). If you could use [0-128) then you could just directly use the bits and XOR the key stream with the plaintext.

Answer 2

Your input alphabet is 95 chars, within the 128 character 7-bit ASCII space. You need the ciphertext to specifically be within the 95 char input alphabet. I assume the microcontroller byte size is 8-bits, and I hope you have 32-bit registers.

The best solution would be to use a 6-bit output alphabet (64 entries) and use an intermediate conversion between the input and OTP to perform XOR. You will of course run into a space penalty as your input is not within the 6-bit encoded space, but it will make up for it with the performance of the algorithm, which is quite quick.

The OTP can be stored as 8-bit per char raw data to save space and read in 6-bit intervals (24 bits = 3 bytes or 4 6-bit chars), or stored as 6-bits per byte. If you stored the OTP as encoded ASCII, it will need to be converted back into a 6-bit stream representing the index of the characters in the alphabet. If you store as 8-bit, you do not have to perform the intermediate conversion before XOR on the OTP, which you will need to do if it is stored as 6-bit.

The plaintext will be converted into a 6-bit stream either from its byte data (8 bits of data, read 6 at a time) or from an encoded 7-bit representation of the first 128 ASCII chars (7 bits read 6 at a time). If the microcontroller has 32-bit registers, you can pack 4 7-bit characters or 5 6-bit characters. 16-bit registers get you 2 7-bit or 6-bit characters. Now you can XOR with the OTP, and you can use several performance-space tradeoffs. You can read the OTP into the full register space (32-bits OTP for 28 or 30 bits of plaintext, 16-bits OTP for 14 or 12 bits of plaintext) and truncate after XOR. Or you can read the exact amount of bits from the OTP as required, which requires additional shift operations but uses less pad data.

After XOR, pack the result 12 or 24 bits at a time, and encode to a 6-bit printable alphabet. I have a high performance alphabet that allows me to use integer operations to encode instead of table lookups like Base64, if your processor is slow at lookups the integer method can be several times faster.

Treating the 7-bit input alphabet as 8-bit entries before encoding is faster, but you loose 1 bit per character of OTP and output space, this may be useful if storage and bandwith is plentiful but you want lower computation or code size. Using 6-8 and 8-6 for input, output, and OTP data means less code, and more simple algorithms:

Input = 7-bit printable ASCII
Inter1 = 8-bit (0 || input char)
Inter2 = 24-bit packed integer (3 x Inter1)
OTP = 6 or 8-bit data
InterOTP = 24-bit packed integer (24 bits of OTP)

XOR integers, encode resultant 24-bits to 4 6-bit characters (65% efficient)

24-bits of OTP, 32-bits of ciphertext used for 21 bits of plaintext

If you want better efficiency, the input is treated at 7 bits instead of 8. You can read full bytes of OTP if you do not need efficiency of pad storage:

Input = 7-bit printable ASCII
Inter2 = 28-bit packed integer (4 x input char)
OTP = 8-bit data
InterOTP = 28-bit packed integer (32 or 28 bits of OTP)

XOR integers, encode resultant 28-bits to 5 6-bit characters (70% efficient), or treat 3 28-bit blocks as 14 6-bit chars (maximum 75% efficient)

28-bits of OTP, 40-bits of ciphertext used for 28 bits of plaintext or
32-bits of OTP, 40-bits of ciphertext used for 28 bits of plaintext or
84-bits of OTP, 112-bits of ciphertext used for 84 bits of plaintext or
88-bits of OTP, 112-bits of ciphertext used for 84 bits of plaintext

There are more space efficient methods, but the computation cost is astronomically high, and unsuitable for a microcontroller. You can pack 9 characters of 95-char alphabet into a 64-bit MMX register using extended precision FP math, encrypt with 64-bits of pad, and encode back into 10 chars using some VERY ugly and cycle hungry math, but it works and is 90% efficient, well beyond the max 6-bit encoding efficiency of binary data (75%).

Answer 3

Both your ideas for down-converting your key values into a smaller range result in lopsided distributions! (Your second idea gives the value 85 less than 1/85 chance; you seem to have some off-by-one errors in your math.) This can severely impact the security of the one time pad.

No down-conversion is necessary for security; they can only decrease the security if not done well.