Padding the length of the message

[neuhaus]

Please add a feature to allow for padding the length of the message. It will consume some of the perhaps precious pad but it will help against side channel attacks.

[kfogel]

Yup, planning to do, as per the comment change commited in https://github.com/kfogel/OneTime/commit/6b924fb2ed9e07cb3c64d942cf201a1b4b36c10b . Thanks for filing the issue, though; it's good to know others feel this is needed too!

[kfogel]

I should probably summarize briefly what the plan is, as the comment in the code may be more in-depth than most casual visitors have time to read. So:

When encrypting, OneTime is going to jump to the appropriate initial offset in the pad (usually determined from the 'pad-records' file, more rarely from the --offset flag) and then read "a few" bytes. It will then convert those bytes to an integer modulo N in some deterministic, platform-independent way. Call the resulting number Q. OneTime will then skip ahead Q bytes in the pad before commencing encryption.

Without knowing the pad (thus, without knowing Q), even an attacker who knows the entire plaintext cannot determine the pad range used for encryption, and thus cannot substitute some other message for the plaintext. This avoids the known-plaintext message authentication problem.

If it wouldn't make the code so messy, I'd do this on bit boundaries rather than byte boundaries, to use up less pad; however, paying some pad to keep the code readable seems like the right tradeoff here. Note that skipping ahead Q bits and then adjusting the offset by P < 8 bits in order to sit on an octet boundary doesn't help: that just makes the distance jumped 8 times more predictable than it would otherwise have been -- in other words, it's like dividing the possible range of Q by 8. The choices are to change OneTime to do encryption starting at arbitrary bit offsets (hard, I think, though will ponder it some more before making a final decision), or skip bytes instead of bits (definitely easy).

[kfogel]

Work on this issue is now happening on the issue-2 branch (https://github.com/kfogel/OneTime/tree/issue-2).

[kfogel]

This is fixed now in the repository. Connectivity problems are preventing me from updating the version at OneTime's home page, but I'll finish that as soon as I'm able. Closing this issue.

[kfogel]

For reference: a verbose description of the problem, and the solution, are now in comments in the source code. See the comments in Pad._make_fuzz_length_from_pad() and Pad._make_inner_header().

[kfogel]

Whups -- the solution currently in the code doesn't work: in the known-plaintext case, the attacker can count backwards from the end of the encrypted message. Reopening this issue.

Possible solutions:

1. Add pad fuzz on the other side as well, of a length also dependent on some data drawn from the pad (though not the same length as the front fuzz, because we don't want the ciphertext simply centered between two equal-length regions of fuzz). Adding fuzz on the end is easy when encrypting: just add it once there's no more input. But to subtract it when decrypting, we'll probably have to buffer the output (since we don't know when the ciphertext input will end, we have to reserve enough output to lop off the fuzz at the end; we do know its length in advance, at least, since that comes from pad data collected before any data conversion is done). The silver lining is that the infrastructure is now in place to make this a fairly easy change.
2. Don't skip lengths at all -- just do message authentication the simpler way: grab some bytes of pad data initially, and use them to calculate either a rolling checksum or a recurring checksum against the data being encrypted, and insert the checksum (encrypted against the pad of course) into the stream in the appropriate places. When decrypting, check it. Strictly speaking, it would satisfy message authentication to calculate a checksum of pad data only, and encrypt the checksum (say, right before the encrypted plaintext). Not sure yet if there's any advantage to including the plaintext as well in calculating the checksum -- pondering. Frankly, I like 2 better. If we want some length disguise, there can still be a random skip length at the front.

[kfogel]

Those recent commits are gonna get squashed before I merge to master, just FYI.

[kfogel]

This is finally done. 2.0-beta6 is the current release candidate, and, barring unexpected discoveries in testing, will become the 2.0 release soon.