5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ OTP has very specific requirements: Truly random keys, no reusage and drawn from a uniform distribution (exactly uniform). Anything that does not match just one of these is not an OTP any more. $\endgroup$ – tylo Mar 17 '17 at 14:10
  • $\begingroup$ @tylo: i'm using a hardware rng built into the microcontroller, which provides excellent (i've tested it ad nausuem) random in 32bit chunks; the hard part is not screwing up the deployment... $\endgroup$ – dandavis Mar 17 '17 at 15:49
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the maths, very insightful. Given that 255 mod 85 = 0 , and that I'm short on CPU power, 85 "letters" looks like a better option than "reshuffling" bits of my random bytes; if input range is restricted to key range, is 85 any less safe than 95? My gut says no, but i'm not competent... $\endgroup$ – dandavis Mar 16 '17 at 22:21
  • $\begingroup$ @dandavis Moved comments to answer. $\endgroup$ – Maarten Bodewes Mar 17 '17 at 9:23
  • $\begingroup$ thanks for the detailed guidance above, i managed to get it working perfectly using an X of 32; i might revisit, but it's good to see ENT happy and my hi/lo values balance as expected with perfect random... $\endgroup$ – dandavis Mar 18 '17 at 0:35
  • $\begingroup$ nice answer, you could add this is named rejection sampling en.wikipedia.org/wiki/Rejection_sampling $\endgroup$ – daniel May 22 '17 at 13:35
  • $\begingroup$ and an alternative exists to rejection sampling, something something probability integral transformation math.stackexchange.com/q/2249929/438622 $\endgroup$ – daniel May 22 '17 at 13:36
3
$\begingroup$

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%).

$\endgroup$
  • $\begingroup$ It's an ESP8266, XOR perf is ample; the key-gen while serial syncing while saving to flash is the pinch. Pre-computing the pad might change the math; you've given me even more to consider. Thanks! $\endgroup$ – dandavis Mar 17 '17 at 6:07
  • $\begingroup$ That's a lot of answer, but in the end you're not in the range [0-95), which in this case was set as a precondition in my opinion. It might be that dandavis was not completely aware of the implications of using a range [0-95) though. $\endgroup$ – Maarten Bodewes Mar 17 '17 at 9:20
  • $\begingroup$ @MaartenBodewes 0-63 is still within that range, is it not? $\endgroup$ – Richie Frame Mar 17 '17 at 12:19
  • $\begingroup$ Yes, if the plaintext input and output characters can be put within that range then this is certainly the best option. Otherwise [0-128) would also be good of course. But if the input is [0-95) and the key is [0-64) then there are quite obviously problems. $\endgroup$ – Maarten Bodewes Mar 17 '17 at 12:54
  • $\begingroup$ this is frankly the most useful answer, and i will be referring to it a lot in the near future, but i think Maarten's is more directly related to the question and was earlier, all else being equal. very much appreciated and insightful answer though, keep up the good work! $\endgroup$ – dandavis Mar 18 '17 at 0:38
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ i get 3 hits for each 0-84 slot when looping 0-254 with int(x / 3); what's the issue? $\endgroup$ – dandavis Mar 17 '17 at 6:30
  • $\begingroup$ Where does 0-254 come from? A byte has a value from 0 to 255, for a total of 256 possibilities, which isn't divisible by 3. $\endgroup$ – Macil Mar 17 '17 at 7:59
  • $\begingroup$ i really should pay closer attention to what i post, but that gives me the idea that i can simply re-roll if 85 comes up, and keep the rest. or maybe i should quit while behind and just store full-byte hex pairs... $\endgroup$ – dandavis Mar 17 '17 at 8:44
  • $\begingroup$ I think it would be best for you to leave the key values untouched; it's secure. If it's size/efficiency you care about, then keep leaving the keys untouched and instead focus on packing the plaintext characters into fewer bytes (you could easily fit two 0-95 values in one byte, etc). $\endgroup$ – Macil Mar 17 '17 at 18:43
  • $\begingroup$ you're probably right, but unfortunately to send pads safely over serial w/ the current setup, they can't use 2 different control characters. i think i have a 95 char routine working, based on Maarten's steps and (heh) converting each 32bit into a 0-94 value (skipping the 6/4bn that roll over)...You did help me get the 84 working though, and i might use it since i learned how to safely extract bytes from that good 32bits. I was very short on sleep earlier, i'm not that dumb, and this is the only part i could screw up, but i agree 110% that "noobs" should be presumed guilty. $\endgroup$ – dandavis Mar 18 '17 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.