Ask HN: I’m writing an OTP encryption algorithm. Where should I ask for review? | Hacker News Reader

Ask HN: I’m writing an OTP encryption algorithm. Where should I ask for review?

9 pointsalanh24 comments

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?

View on HN

"This might be less stupid than it sounds"

No, 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.

The stupidity of an exercise should be measured upon its motivations. If OP is doing this for entertainment or for their own education then it is far from stupid.

Here in Ukraine, we have a nice saying: "Don't rush into the hell before your father".

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.

"For it to exist, the sequence must pass a row of tests."

Sorry, that's laughable.

"even /dev/random will do"

It's just not OTP anymore, but who cares?

Why is it laughable? I'm not disagreeing with you: I am rather curious.

Because information theoretic security is a property of a randomness source, not its output data. And it has a stringent definition.

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.

Could you provide the stringent definition regarding the randomness source, not a cryptosystem?

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.

The randomness quality is part of OTP's definition, so your "random enough" and "considered safe" places you squarely out of OTP territory, back into "homegrown stream cipher".

Then why are you avoiding providing this definition here?

Have you ever read how /dev/random data are actually gathered and how do they differ from /dev/urandom?

Nice try. ;-)

http://www.2uo.de/myths-about-urandom/#computationally-secur...

In fact, nothing prevents us to lay a custom layer of gathering the entropy over (u)random, so all the issues mentioned in that article can be easily circumvented.

If I had a license and enough money to buy Gryada-3 module, I certainly wouldn't look into any pure-software solutions.

Forgot to answer this:

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

> Let's consider we've produced exactly 4 GiB of random key data and distributed it between the two users

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

Because that method doesn't imply the key distribution channel will be available 100% of the time. In fact, it implies the opposite: one-time transmission. For the next 4 GiB, it would be wiser to switch the channel. Between these two occasions, we have plenty of time.

It doesn't matter.

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.

It does matter. You can, for example, initially share the key data on a pinlocked pendrive. What would be really impractical is using this pendrive to transmit actual messages.

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 understand that a secure pen-drive (which is what I think you're talking about by 'pinlocked') has a HSM (Hardware Security Module) with hardware implementations of standardized encryption algorithms, right?

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.

> You literally just suggested using standardized encryption algorithms to protect your OTP key.

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.

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

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".

If you can really see beyond the algorithms, you should understand what I mean.

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.

It's a hard problem, not an impossible problem. Naval ships would have code books distributed to as recently as the 1970s.

I don't have time for exactly reviewing your algo and implementation, but I'd like to be sure:

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.

There's an active cryptography mailing -- http://www.metzdowd.com/mailman/listinfo/cryptography. You might try there, but I wouldn't get too excited as you may know, cryptography professionals look suspiciously to the amateurs rolling their own crypto. My own warning: algorithm itself is not the hardest part, a bug free, safe from side-attacks implementation is.

Reply on news.ycombinator.com