Teensy weensy crypto

https://blog.goeswhere.com/2015/11/nano-rc4/

by sadiq • 11 years ago

112 56 11 years ago

blog.goeswhere.com

seanwilson• 11 years ago

As the UK's politicians continue to fail to understand what "strong cryptography" or "banning" even mean, I thought I would have a look at how simple strong cryptography can be.

Not that I think it's a good idea or believe they have a good understanding of cryptography but: if they are being rational about it, I'm guessing they think making strong cryptography less convenient will lead to less encrypted communications between parties they're interesting in snooping on. In this case, WhatsApp would be a considerably more convenient to use than using DOSBox.

mtgx• 11 years ago

Yes, the UK gov argument is basically "You can keep your PGP, just run Gmail, Facebook, Skype, etc over HTTP - or at least let us automatically remove the HTTPS encryption for anyone we want in real-time".

They want it this way because:

1) many people will indeed slip when using whatever left is there of "strong encryption" afterwards, especially if it's hard to use - that's pretty good for the UK gov.

2) while they may care about terrorists and whatnot, they care at least as much about spying on many of the people who will never use PGP or even Signal, so again this plan is perfect for them in this regard.

toyg• 11 years ago

In fact, this plan's only purpose is average-citizenry monitoring. Terrorists and child pornographers already have such an understanding of how to use crypto (or how not use electronic communications at all, like Osama staying offline most of the time -- this is also what mafia bosses do, btw) that they will be completely unaffected. If that weren't the case, bombs would be going off every day all over Britain, and they just don't.

The Snooper's Charter exists just to keep uppity citizens and low-rent drug dealers under control.

johansch4• 11 years ago

The writer of this is confused. The UK politicians don't care about whether something is trivial or not, all they want is to ban it.

Sort of like making a fire is trivial, and it's illegal to do so in many places.

thescriptkiddie• 11 years ago

This isn't about the triviality of implementing rc4, it's about the absurdity of banning information in a general sense.

Information can be copied at zero cost, transmitted instantly over vast distances, and stored permanently and undetectably in the human brain. Information spreads like a virus in a very literal sense - you overhear a scrap of plot and suddenly a whole film is spoiled. Trying to ban information is a futile as trying to arrest people for catching influenza. This isn't like banning campfires, or even like banning firemaking implements, it's like banning the very idea of fire.

johansch4• 11 years ago

Again you are missing the point.

We see it that way, they don't. We certainly won't win this battle by trying to teach them information theory (good luck! :) )

declan3• 11 years ago

Sort of like making a fire is trivial

Yes, but demonstrating the practical difficulty in trying to regulate 102-byte sequences that can fit on a T-shirt (or in a tweet) has a utility of its own.

It's what Prof. Dave Touretzky did in the case of DeCSS, which got shrunk down to 434 bytes when implemented in C: https://www.cs.cmu.edu/~dst/DeCSS/Gallery/

johansch4• 11 years ago

Yeah, the same sorta utility it has to demonstrate that it is possible for anyone to create a fire in any publicly accessible location in London, for instance in some very valuable historic building. (No, I am not advocating you do so.) I'm just making the point that you didn't get my point. They don't care about how feasible or trivial something is as long as they can ban the usage of it.

In legal terms: all you are doing is irrelevant technical wanking.

lectrick• 11 years ago

They're basically banning a (long) number.

Which is absurd. I thought we hashed this out when DeCSS was a thing.

mappu• 11 years ago

My initial disassembly: https://gist.github.com/anonymous/af0d79474929340a7bf0

lisper2• 11 years ago

Just in case anyone is tempted to actually use this and hasn't gotten the memo: RC4 is broken and has been for some time now.

nothrabannosir• 11 years ago

Any comment on this?

Is RC4 secure? For this use-case, yes. For TLS, most certainly not. Even today there are many plausible attacks against RC4 in the TLS context, but none of them apply to this static-data world.

aidenn02• 11 years ago

RC4 is no longer considered secure for most any purpose. There is known bias in the first few bytes of the cipher that can allow for key-recovery with enough messages sent with the same key. In general you want "head room" in your ciphers such that the best attacks today are not just impractical, but wildly impractical, because attacks tend to get better over time.

RC4 was known to not have this "head room" for a while, and now is largely broken.

mikeash3• 11 years ago

Let's say you wanted to implement a more modern, not (yet?) broken algorithm instead of RC4. Are there any which could fit into a similarly small amount of code?

swiley• 11 years ago

RSA is pretty short (just modular exponentiation). The problem is all the stuff that goes around it: key generation, padding etc.

JoachimSchipper• 11 years ago

With Intel's instructions, AES-GCM is decently short. ;-)

Rebelgecko• 11 years ago

Maybe not quite that small, but if you look up some "lightweight block ciphers", you can find some candidates.

lisper2• 11 years ago

I like TEA (or XTEA or XXTEA). Not quite as small as RC4 but still pretty compact.

https://en.wikipedia.org/wiki/Tiny_Encryption_Algorithm

hatsunearu• 11 years ago

https://en.wikipedia.org/wiki/Speck_%28cipher%29

Speck's pretty nice and tiny, but who knows if it's backdoored or not :)

sdevlin2• 11 years ago

With this (and your computer) you can secure a message with a password in a way that's unbreakable. I can't break it, your government can't break it, other people's governments can't break it. Secure.

Argh. No.

Should you use it? No. There's many important missing features that are present in proper symmetric encryption tools, such as proper key derivation, protection against modification, IVs, and fewer bugs.

This (buried) warning makes these things sound like bells and whistles. The truth is they're essential to security.

Here are some good reasons not to use this for anything:

1. It conflates passwords with keys. Users will not choose high-entropy passwords when left to their own devices.

2. It doesn't take an IV. This means a given password will always generate the same key stream, which means password reuse will lead to plaintext recovery by simple statistical methods. There are no warnings about this.

3. It's not authenticated. An attacker can modify messages in flight with unexpected consequences that very often include plaintext recovery.

4. RC4 is irreparably broken. Dropping 1024 bytes from the key stream might help in the author's intended use-case (assuming users adhere to it), but this is not an effective mitigation in general. The best attacks on RC4 rely on periodic biases that persist over the entire key stream.

s_tec• 11 years ago

Right, but the goal isn't to make a strong or useful encryption tool. The goal is to show that cryptography is, at it's core, rather simple. It's simple enough that we can cram "real" symmetric encryption into the size of a tweet.

It's like building an electric motor out of some scrap wire and some fridge magnets - the motor isn't really useful for anything, but it teaches the basic idea in a way that anybody can appreciate. A useful motor would have bearings, a commutator, multiple windings, an iron core, etc., but adding all that stuff just obscures the basics. Criticizing a school-kid's motor for being weak and inefficient is completely missing the point.

This program isn't supposed to be useful. It's supposed to prove a point.

tptacek3• 11 years ago

Is RC4 secure? For this use-case, yes.

That was the point where I went to go write an HN comment, before seeing that Sean had already written it.

Is RC4 secure? No.

sdevlin2• 11 years ago

If that is true, the author should avoid words like "secure" and "unbreakable".

DanBC4• 11 years ago

but the goal isn't to make a strong or useful encryption tool
> With this (and your computer) you can secure a message with a password in a way that's unbreakable. I can't break it, your government can't break it, other people's governments can't break it. Secure.

Some governments execute their citizens. If a crypto tool is neither strong nor useful it probably shouldn't be described as such.

stupidcar• 11 years ago

You consider a qualification four paragraphs into an article “buried”? Christ. I know attentions spans are short these days, but that's pretty pathetic.

You're acting like the author proposed this as a serious encryption tool, but no sane person could read this article and reach that conclusion. You're only feigning to believe it in order in order to have an excuse to show off your supposedly superior knowledge of encryption.

eliteraspberrie• 11 years ago

If you have one of the three:

1. a one-way hash function; 2. a block cipher; or 3. a secure random number generator;

then you have the other two.

So replace "RC4" with Keccak and the argument stands. Keccak doesn't fit in a tweet but it prints onto a single page, which is easy enough to distribute: https://github.com/gvanas/KeccakCodePackage/blob/master/Stan...

fryguy• 11 years ago

Without an IV, it's laughably easy to reconstruct the plaintext from multiple messages with the same key. Probably as few as a handful.

That being said, I agree with the other people -- this isn't a "real" thing. It's just something to show how ill-conceived a plan to "ban encryption" is.

746F7475• 11 years ago

You are talking about "users" a lot, I doubt the author actually tried to suggest that this was used in some kind of "product" rather that if a encryption can be spread via tweet it makes no difference how you try to ban it's usage, the bad actors ARE going to be able to encrypt their messages, you are just banning honest citizens usage.

Potential bannable use-case for this "bad crypto" is some criminal organization messaging each other and if they are smart enough to use this they can also come up with good password which makes the banning again completely irrelevant and the kicker is that criminals aren't going to use this "bad crypto" they are going to use something even stronger

declan3• 11 years ago

This reminds me a little of [edge|base|corner] cases in programming. It's easy to handle normal parameters. But if you're at or beyond the limits of expected parameters, then what? If you ignore [edge|base|corner] cases, you run the risk of enacting a bad law.

So if a government wishes to restrict encryption, does that mean criminalizing only the distribution of commercial products with strong crypto? Or knowing possession of them? How about if you distribute free software? Possess free software? How about distributing an algorithm that's printed out? On a t-shirt? Set to music? In a sonnet? On a blackboard in a math lecture?

A crypto-ban proposal discussed in the U.S. Congress stopped short at targeting possession, but did target "import[ing]," which presumably would include downloading from an offshore site:

"It shall be unlawful for any person to manufacture for distribution, distribute, or import encryption products intended for sale or use in the United States..." http://thomas.loc.gov/cgi-bin/cpquery/T?&report=hr108p4&dbna...

Diederich• 11 years ago

Surely some of the folks here also wore the Perl RSA implementation on a t-shirt back in the mid 90s:

http://www.cypherspace.org/rsa/

A lot of comments here are talking about how the author is mistaken about the security of RC4.

The point of this post, and the t-shirt, is that it's dumb on many, many levels to ban cryptography.

infinity0• 11 years ago

It looks like this is the next step in the British tech community's long road of denial to hell: smug overconfidence tightly coupled with plain ignorance.

The blog post makes an absolute fundamental mistake about security in cryptography, and even when corrected you trivialise the correction! Let me make it absolutely clear: the blog post author has no idea what he is talking about and his words disqualify themselves.

"Is RC4 secure? For this use-case, yes."

This is absolutely not an even faintly correct statement to make. NO IT IS NOT SECURE. When a cipher is developed, there is some belief on the cost of attacking it. As time goes on we gain more knowledge about it, and the believed cost for RC4 today is pretty much trivial. "Cost" refers to the cost of an attack, not the cost of research. What, you think that because the research (that has already been done) was hard, that attacks are hard? Classic naive "[in]security argument" fallacy. Also, what the fuck does it even mean to say "For this use-case" on a public blog???

There are actual formal precise definitions of "security" in crypto. Learn them. If you don't know them, you can't possibly hope to draw the correct conclusions about what cryptography actually is, and what one does with it, and you should not make wildly inaccurate public blog posts that only serve to further confirm the ignorants' own beliefs.

Yes, it is possible to make lives so hard for non-ignorant real cryptographers doing actual research, such that the economy effectively has no strong cryptography. Then you don't need to ban it outright. So dismissing this attempt by the UK government is extremely naive and dangerous.

But hey, this might backfire as good cryptographers leave the UK and head elsewhere, and the UK economy ends up with people that don't know shit about what security means.

distantsounds• 11 years ago

I'm unsure why all the ranting against DOSbox - why not just run MS-DOS in a VM? what are you gaining out of using DOSbox, aside from copy-paste support?

arantius• 11 years ago

Wouldn't Solitaire [1] be a better argument (of this vein) against banning encryption? It's reasonably strong and doesn't even require a computer. Much more practically memorized.

[1] https://www.schneier.com/solitaire.html

Teensy weensy crypto

Related Stories