Ask HN: I’m writing an OTP encryption algorithm. Where should I ask for review?
I have always heard and respected the advice: Never roll your own crypto! Well, I’m planning to roll my own crypto. This might be less stupid than it sounds as it ’s going to be a glorified one-time pad, and one-time pads have the delightful properties of being incredibly simple to understand and also completely unbreakable (if used properly).
It’s the parenthetical condition above that worries me, and I’d be grateful for some peer review after I finish the first version of my algorithm.
I don’t hang out in crypto circles, so I thought I would ask HN: Do you have suggestions for communities, persons or entities who might be interested in reviewing my algorithm and implementation?
24 comments
[ 1.5 ms ] story [ 59.4 ms ] threadNo, it is even more stupid than it sounds, because
"as it’s going to be a glorified one-time pad"
One-time pads are impractical. You need a key that's as long as your message. Pre-shared. You need "information-theoretic security" of your random numbers (that's extraordinary!). You must never ever re-use the key.
Exactly 100% of One-time pads that people code are simply badly done stream ciphers, not One-time pads.
I.e. don't make any prejudiced conclusions before you get any single answer.
I am too in a doubt that the OP sees the diference between OTP and SSC, but he has to answer himself.
Cryptography was my primary speciality in the university, and I know for sure that "information-theoretic security", i.e. degree of randomness, of a bit sequence, isn't a rocket science. For it to exist, the sequence must pass a row of tests. It's not so hard to achieve. Finding the actual entropy source is much harder. Without a dedicated chipset (have you ever heard of Gryada-3 (Гряда-3, roughly translated as Ridge-3) RNG module? Probably not, it's a Ukrainian invention), human interaction (mouse movement etc) or using external sensors (temperature deviations, for example) the only entropy source I can think of is RDTSC timestamp gathering.
For us mere mortals, even /dev/random will do. But the most interesting question for me is how the hell (which you shouldn't rush into before your father) the OP is going to distribute and sync the random pile of data. That alone is quite a hard problem, especially if the pile is distributed between more than two users.
So let's be patient and wait for the answers.
Sorry, that's laughable.
"even /dev/random will do"
It's just not OTP anymore, but who cares?
The idea that "I'm throwing the output of some randomness source at Diehard, and if Diehard says it's good then the source provides information theoretically secure random numbers" is a category error at best.
I see it as this: if the randomness source cannot be one more time put into the same conditions that it would start repeating the same sequence, and its output is random enough (i.e. passes the tests), it may be considered safe for OTP key data production.
http://www.2uo.de/myths-about-urandom/#computationally-secur...
If I had a license and enough money to buy Gryada-3 module, I certainly wouldn't look into any pure-software solutions.
> One-time pads are impractical. You need a key that's as long as your message. Pre-shared.
Need in a key as long as your message (pre-shared) doesn't mean that OTP is impractical.
Let's imagine a conversation between two users that exchange tweet-sized messages in Latin-1 encoding (i.e. each plain message weighs no more than 140 bytes).
Let's consider we've produced exactly 4 GiB of random key data and distributed it between the two users (on a pendrive or somehow else).
When the message is received, its encrypted length is the same as the raw length, so we just move the key pointer for the message length on each send and reception.
So how many 140-byte messages can be sent with 4 GiB of key data? Math.floor(4 * 1024 * 1024 * 1024 / 140) = 30678337.
So, 4 GiB of pre-shared key data allows us to send over thirty millions of tweet-sized messages for both sides. How in the world is this impractical? Especially at our days when a 16 GiB file is a norm.
And yes, pre-sharing these key data can involve a simple SSC, BSC etc. It might be hard for an attacker to figure out when to stop when he constantly gets a random garbage out of the same-looking random garbage.
if you have a method of securely distributing 4gb of key, why on earth wouldn't you use that to transmit the message itself?
That's 100% impractical
In order for OTP to work, you first have to invent secure communication. It puts the horse before the carriage.
Oh, and now you have to maintain perfect secrecy/privacy of a 4gb file.
Solved one problem (theoretically), and now you have a multitude of practical issues.
So again, OTP is impractical.
Whether OTP is practical or not, entirely depends on real-world conditions.
P.S. Tell all this to the OP, not me. I'm not building an OTP system.
You literally just suggested using standardized encryption algorithms to protect your OTP key.
Or you could...you know...just use standardized crypto across the board.
OTP is by definition impractical. I'm sorry that you don't see that.
I suggested using standardized (or non-standardized, but other than OTP) encryption algorithms for an initial key data distribution channel that completely differs from the main communication channel and exists for a relatively short period of time. That's my key point.
> Or you could...you know...just use standardized crypto across the board.
I'm not going to dive deep into the topic of why I consider "just using standardized crypto" unsafe and prefer rolling another custom end-to-end encryption layer on top of it.
> OTP is by definition impractical. I'm sorry that you don't see that.
I'm sorry that you can't see beyond the algorithms. We're far ahead of the time when OTP was the only active instrument (aside from straddling checkerboards and Enigmas). Modern crypto can be combined in such a way that every encryption scheme finds its natural place. I honestly don't see why OTP cannot have one.
please, by all means, enlighten us.
> I'm sorry that you can't see beyond the algorithms.
Please keep in mind that you have no idea what my background is (or what experience I have), so don't assume that I "can't see beyond the algorithms".
Exploring a "spherical algorithm in the vacuum" begins being useless at some point. One should explore its properties when used in a real environment. Protocols where OTP usage is plausible and practical definitely exist. I'm not saying that OTP is practical for every possible use case though. In fact, in my first comment here I had asked the OP about how he's going to solve key distribution problem among multiple users. Because when such a simple algorithm is used, the actual protocol matters much more.
What's your algo supposed to do?
One-time-pad, you know, is just a system of distribution and usage synchronization of truly-random key data. The key data itself cannot be generated with any algorithm. If they are, it's not a one-time pad, it's a stream symmetric cipher.
So, if you are going to really write an OTP implementation, I have to ask the first question one more time: what is your algo supposed to do?
The second question: how do you create a random keystream in order for it to be truly random, not pseudorandom?
And the third question: how are you going to distribute and synchronize that random pile?
Answers to these three questions would certainly increase the interest in reviewing your algorithm and implementation.
Thanks in advance.