## Spritz: A New RC4-Like Stream Cipher

Last week, Ron Rivest gave a talk at MIT about Spritz, a new stream cipher by him and Jacob Schuldt. It’s basically a redesign of RC4, given current cryptographic tools and knowledge.

RC4 is an example of what I think of as a too-good-to-be-true cipher. It looks so simple. It is so simple. In classic cryptographic terms, it’s a single rotor machine. It’s a single self-modifying rotor, but it modifies itself very slowly. Even so, it’s very hard to cryptanalyze. Even though the single rotor leaks information about its internal state with every output byte, its self-modifying structure always seems to stay ahead of analysis. But RC4 been around for over 25 years, and the best attacks are at the edge of practicality. When I talk about what sorts of secret cryptographic advances the NSA might have, a practical RC4 attack is one of the possibilities.

Spritz is Rivest and Schuldt’s redesign of RC4. It retains all of the problems that RC4 had. It’s built on a 256-element array of bytes, making it less than ideal for modern 32-bit and 64-bit CPUs. It’s not very fast. (It’s 50% slower than RC4, which was already much slower than algorithms like AES and Threefish.) It has a long key setup. But it’s a very clever design.

Here are the cores of RC4 and Spritz:

RC4:

1: i = i + 1
2: j = j + S[i]
3: SWAP(S[i];S[j])
4: z = S[S[i] + S[j]]
5: Return z

Spritz:

1: i = i + w
2: j = k + S[j + S[i]]
2a: k = i + k + S[j]
3: SWAP(S[i];S[j])
4: z = S[j + S[i + S[z + k]]]
5: Return z

S is an 8-bit permutation. In theory, it can be any size, which is nice for analysis, but in practice, it’s a 256-element array. RC4 has two pointers into the array: i and j. Spritz adds a third: k. The parameter w is basically a constant. It’s always 1 in RC4, but can be any odd number in Spritz (odd because that means it’s always relatively prime to 256). In both ciphers, i slowly walks around the array, and j—or j and k—bounce around wildly. Both have a single swap of two elements of the array. And both produce an output byte, z, a function of all the other parameters. In Spritz, the previous z is part of the calculation of the current z.

That’s the core. There are also functions for turning the key into the initial array permutation, using this as a stream cipher, using it as a hash function, and so on. It’s basically a sponge function, so it has a lot of applications.

What’s really interesting here is the way Rivest and Schuldt chose their various functions. They basically tried them all (given some constraints), and chose the ones with the best security properties. This is the sort of thing that can only be done with massive computing power.

I have always really liked RC4, and am happy to see a 21st-century redesign. I don’t know what kind of use it’ll get with its 8-bit word size, but surely there’s a niche for it somewhere.

Very interesting!

Alan Kaminsky October 27, 2014 12:47 PM

@Bruce: I don’t know what kind of use it’ll get with its 8-bit word size, but surely there’s a niche for it somewhere.

Considering the vast array of places where RC4 is being used right now, I wouldn’t characterize RC4 as a “niche” cipher. Spritz is a drop-in replacement for all of those.

As just one example, RC4 and Spritz are very easy to implement in JavaScript. This means that encryption or decryption code can be embedded in web pages and run in the user’s browser, gaining end-to-end encryption of sensitive data without relying on SSL/TLS and its many bugs. Try doing that with AES. It can be done, but oh the pain.

Bruce Schneier October 27, 2014 1:25 PM

“Considering the vast array of places where RC4 is being used right now, I wouldn’t characterize RC4 as a ‘niche’ cipher. Spritz is a drop-in replacement for all of those.”

That’s a good point. RC4 is pretty much the only stream cipher in general use, and this is an easy drop-in replacement in all those cases.

parrot October 27, 2014 1:36 PM

@Alan Kaminsky

At the risk of derailing the topic from Spritz…

Isn’t the notion of re-downloading your cryptographic implementation each time you visit a site fundamentally broken in terms of satisfying end-to-end encryption needs? I mean, if the threat model is that someone compromised the server, and you don’t want your data being compromised as well, wouldn’t the attacker also be able to just change the Javascript served to you to be the null cipher?

In other words, if you don’t trust the security of the server, don’t trust the code the server gives to you.

Maybe this makes sense for browser plugins or Greasemonkey-like scripts? I don’t know.

A Nonny Bunny October 27, 2014 1:55 PM

@parrot

Isn’t the threat model mostly passive eavesdropping? There’s certainly a risk a man-in-the-middle could change the javascript code you receive, but it’s not the most common one. And on the plus side, the algorithm is simple enough to check.

Aside from that, there’s also the Mega use-case, where the server simply wants to be agnostic about the crap you’re uploading.

parrot October 27, 2014 2:23 PM

@A Nonny Bunny

Isn’t the threat model mostly passive eavesdropping?

No, that should be covered with TLS.

Aside from that, there’s also the Mega use-case, where the server simply wants to be agnostic about the crap you’re uploading.

I think this is the threat model @Alan Kaminsky was suggesting (though he could prove me wrong). I presume being agnostic means that if a government implicates or extorts the service for holding illegal data, they can wash their hands of the issue because they don’t have the keys.

What I’m suggesting is, for example, the FBI sends the service a National Security Letter to that service saying “Hey, change the Javascript implementation to this weaker one.”

And on the plus side, the algorithm is simple enough to check.

How would a browser check that? With integrity checking code also provided by the server as Javascript? Then the NSL would just have “…and change the checking code, too.”

Or are you suggesting a manual check of the algorithm? But, that would have to happen every time you pulled new code from the server. And since Javascript is more or less dynamic, who’s to say that the semantics of the algorithm can’t be changed without changing the core encryption functions?

I think end-to-end requires more integration into the browser or other external tools.

I was hoping that this would be the year that admins started switching en mass from RC4 to the Snuffle family for their stream cipher needs. It’s now been 9 years since the eStream contest so they have almost a decade of crypto-analysis behind them. djb is also trusted and respected in the community for his critical and innovative work in elliptic curves, implementation vulnerabilities and the fact that he’s an academic (as opposed to being a government or commercially employed cryptographer). Ron even suggested Salsa20 during his “Growth of Crypto” talk at Princeton’s Alan Turing centennial.

I hope Spritz doesn’t derail that migration.

Anura October 27, 2014 4:45 PM

@anon

Until it is easily broken in the field by someone with reasonable resources (e.g. a botnet), there won’t be an en masse move because so much is implemented in embedded systems which are notoriously slow to update. On top of that, major businesses like banks are reluctant to upgrade. You’ll find most banks still use 3DES for encryption, because it was a lot easier to migrate to it from DES. I wouldn’t be the least bit surprised if 3DES was used more than AES these days.

Upgrading to something that’s a drop in replacement, such as Spritz is going to go a lot faster. For new development use AES, where we probably won’t see practical attacks for at least a couple of decades if at all, but for those legacy systems they are going to go with a drop-in replacement.

All that said, I’d love to see a drop in replacement FOR AES. Something with a bit stronger key-schedule and more rounds. If you can fix some of the weaknesses in the key schedule, it’s possible that you don’t need too many more rounds for it to be secure.

Personally, I would go with 16 rounds for the 128-bit key, 20 for the 192-bit key, and 24 for the 256-bit key. I would personally go for a completely different, and much slower key-schedule, just to provide a larger security margin:

1) Initialize a 32-bit value z to a constant k, initalize a counter i = 0
2) Run each byte of z, XORd to a i through an s-BOX and MDS Matrix
3) For each four-byte chunk of the key, add the key chunk to z modulo 2^32 and then repeat step 2 for each chunk of key
4) Set subkeyi = z
5) Set z = z xor k, increment i by 1. Goto step 2

Much slower, but much less likely to have attacks against it, while still being extremely simple.

Brian October 27, 2014 4:46 PM

I think it’s probably wise to remember that almost all computers in the world are 8-bit. The primary reasons assemblages of circuit boards will remain single security domains are lack of interest in securing them and lack of ability to secure them. The former is rapidly changing as embedded designers realize anything programmable is a vulnerability in a design. The latter is just reality when the center of the design is a 50 cent microcontroller with 2KB flash and 63 bytes RAM. Yes it can fit TEA or XTEA; no it can not fit any known authentication algorithm.

Guy Shaw October 27, 2014 4:56 PM

RC4 does not have to implemented using an array of 8-bit bytes.
It is allowed to use more memory, and store a 256 entry array
of 32-bit words. There are implementations that do that,
because it improves performance, dramatically.

Nick P October 27, 2014 6:22 PM

@ Bruce

I was reluctant to let the RC4 cipher go for lower assurance applications. It was indeed simple & performed well on weak hardware. Yet, it’s time for it to be retired into history. If anything, encryption in practice was often buying the user time against the adversary. RC4 bought enough time for AES, eSTREAM, and SHA-3 ciphers to come out. A number also got close to a decade of cryptanalysis. It was also widely deployed.

So, Rivest et al can still feel proud of RC4’s contribution.

@ anon

Yeah, I’ve been recommending Salsa20. We already have a good stream cipher that’s fast and has an implementation (NaCl) resistant to timing channels. No need for RC4++.

@ Brian

The potential solution is an uptake in the eSTREAM ciphers designed for hardware. Grain has especially low gate count and power usage even at 128 bits with 900Mbps+.

@ Ryan

ISAAC is the shit. I’ve used it for a long time in various ways. I’d like to see more cryptanalysis of it just because it’s worked so well for so long.

@ Anura

You’re definitely right on the 3DES for banks. I encountered this studying IBM’s FIPS Level 4 crypto processor. It’s main library, along with all similar chips, were advertising 3DES for almost everything security-critical. Even a number of government COMSEC devices did that. I was thinking “What the hell people?” Compatibility with existing certified software and hardware implementations of DES seemed to be best explanation.

RC4 transition might be easier, though, because AES is in so many things. The NIST standardization at least had that value for us.

@Nick P & all
I would agree that Salsa20 family by djb is a really good cipher and more RC4++ or whatever it is would make no difference to the reality of security.

Yet another cipher does not solve the real world problem of more ciphers and protocols but no agents to convey it’s security performance and perimeters.

One more to note… patents, trademarks, copyrights might turn out to be an issue with the new Spritz cipher. We know that RC4 and RC6 have trademark, copyrights and trademark issues… so will we see Spritz with same issues too ?

If I were to choose a few stream ciphers fro eSTREAM, they do be Salsa family (primary) and HC family (secondary). HC would be chosen due to the huge internal states and so far there is no solid cryptanalysis breaking it yet and it has been known to be “built like a tank” with huge conservative boundaries.

CTR mode as a stand-in stream cipher would always be a good option as well.

Perl Crusher October 27, 2014 11:06 PM

@Brian

How much then is the 8KB flash 1KB ram upgrade? \$0.52? Though it seems in a large number of cases the \$0.02 can be spent on flash write-enable pads/washer/jtrig/spi/etc to address the programmable vulnerability

Thoth October 28, 2014 1:01 AM

@Nick P
The security industry is more concerned with userbase issues like backwards compatibility and ease of use (including key recovery) than compared to high assurance. We need to thank the powers that be for their efforts of pushing such concepts into the civilian security industry which propagates very successfully into almost every other sector.

Hardware based link encryptors have CC EAL 3+ (no kidding) and are sold as high assurance link encryptors to commercial and government agencies. What a joke …

HSM … CC EAL 4+ (SafeNet and Thales). If HSMs are simply CC EAL 4+ and lower then how is it different from Linux/MS/Mac which are also CC EAL 4+ and lower except they have FIPS 140-2 certification.

Security industry in a general sense is like a rotting apple. Lots of smokes and mirrors and no lack of security theater just for the good \$\$\$ cash \$\$\$ rush.

AES can be used as a stream cipher with a trivial amount of XOR-ing. What’s the benefit of something designed as a stream cipher over using AES this way?

Clive Robinson October 28, 2014 5:52 AM

There is one lesson we should learn, but for some reason we don’t despite all that history teaches us, and that is,

Security Should Not Be Baked In

Whilst in theory encryption systems could be perfect, history tells us that offten they algorithms are not and worse the implementations are any thing but secure.

Thus we have to upgrade the implementation or algorithm on a fairly regular basis.

Thus our designs should alow for such upgrades as a matter of normal operation, not as being so exceptional we have to throw entire systems into landfill.

With the advent of implanted medical electronics, smart meters and the Internet of Things, we realy should mandate via legislation or standards or both that security elements for such things be upgradable in a non invasive but secure way.

It’s something I’ve suggested before that the likes of NIST should be doing in prefrence to having algorithm contests.

I beg the pardon of those who know, but I don’t understand the point of the SWAP instruction in RC4.

Addition is commutative: a+b = b+a, therefore exchanging the two elements in the array seems entirely pointless given that the next thing you do is add them together.

Have I misunderstood something?

Thanks, J.

RC4 is paper&pencil-able with a reduced alphabet, for example the English alphabet,:

1) take 26 symbols of English alphabet and write down each symbol on small pieces of wood or paper;
2) make a key-driven permutation S, and order the pieces accordingly;
3) under the pieces, write down the alphabet normal sequence, one symbol under one piece
4) use two pebbles that roles {i, j} indexes
5) run the algorithm, moving the pebbles on the pieces and on the sequence, and interchanging the pieces whenever necessary

Spritz is harder paper&pencil-able 😉

Jeremy October 28, 2014 12:51 PM

@Jon
That algorithm is run in a loop; the swap operation in RC4 doesn’t affect the current output, but it affects future outputs.

@Guy Shaw
An array containing 256 entries of 32-bit words is going to reduce the entropy of your output by about a factor of 4, because there are only 2^8 possible 32-bit patterns you can output. To do 32-bit outputs “right” you’d need a permutation array containing 2^32 entries, which means you’re now using gigabytes of memory (as opposed to less than a kilobyte in the 8-bit version).

A 16-bit permutation array might be reasonable in some settings (128 KB, if my math is correct).

@clive robinson,

while this is probably semantic nitpicking, I am concerned that a less erudite reader could easily be confused by your usage of ‘baked in’ as conpared to the common usage.

I beg to differ with the proposition that ‘security should not be baked in.’ In common usage, the comparison is ‘baked in’ vs ‘bolted on’. In this usage, baking security in means designing and implementing the system with the intent that it be secure in the first place. Bolting security on, on the other hand, is modifying the application after the fact to be able to hamdle a security need that it otherwise is completely incapable of handling. For example, adding crypto where there is no crypto, or adding the OWASP CSRFGuard in full-auto mode, or usong a Web application firewall . in each of these cases, the app is broken, and the security functionality is poorly integrated into the app.

I would contend that better phrasing would be ‘crypto agility’ if you loke a popular phrase, or ‘configurable and replaceable crypto’ if you don’t. This is complementary to baking security in, in that well architected software is genetally highly modular and often highly configurable. Being highly modular allows for the upgrading of the crypto module of whoch your post describes.

@ Jon: It makes S[] different for the next iteration.

Thanks, @Jeremy & @MrC. Makes more sense that way. J.

Alan Kaminsky October 28, 2014 2:17 PM

@Thoth One more to note… patents, trademarks, copyrights might turn out to be an issue with the new Spritz cipher. We know that RC4 and RC6 have trademark, copyrights and trademark issues… so will we see Spritz with same issues too ?

The Spritz paper that Bruce linked says this on page 25:

“We do not know of any patent or other restrictions on the use of the ideas proposed here. We have not filed for any such patents (and will not). The authors place into the public domain any and all rights they have on the use of the ideas, methods or systems proposed here. As far as we are concerned, others may freely make, use, sell, offer for sale, import, embed, modify, or improve the ideas, methods, or systems described in this note. There is no need to contact us or ask our permission in order to do so. We ask only that this paper be cited as appropriate.”

Maybe some patent troll will come out of the woodwork and claim intellectual property rights, but Rivest and Schuldt won’t.

@Jeremy:

Guy’s post confused me for a good bit. I think what he meant is that you can use 32-bit words internally (together with some modulo math) for a speed improvement; the output is still 8-bit.

I think desktop class devices (including so-called smart phones) should migrate to ChaCha20 but Spritz looks like a good option for embedded systems which run on 8 bit micro-controllers (think fax, printers, implants, chip/pin credit cards).

For these purposes, I’d like to know how it compares to the recently published Speck cipher from the NSA which was tested on a 16MHz 8-bit micro- controller and is also well suites to lightweight implementations.

http://eprint.iacr.org/2013/404.pdf

Any thoughts on Speck vs Spritz?

Nick P October 28, 2014 7:27 PM

@ Thoth

It’s hilarious that you said…

“Hardware based link encryptors have CC EAL 3+ (no kidding) and are sold as high assurance link encryptors to commercial and government agencies. What a joke …”

…because last night I was Googling for high assurance VPN’s to see what pops up and it was a bunch of EAL4 encryptors. I was going to post a gripe about that here but thought: “the only people who would care have seen me say it already so nah…” Anyway, here’s the one I kept stumbling on.

Let’s break this down. It’s a “High Assurance” VPN because it’s been “evaluated and certified… with assurance package EAL4+.” High assurance and EAL4 in the same sentence. Strike 1. Next, we see it can be used only up to Restricted because the government would certainly limit highly assured systems to the lowest NATO classification level there is. Strike 2. Then, what at first seems beneficial, they’re undergoing an EAL5 certification to show they’re a step up from the rest. They might be, but EAL5 is medium assurance not high.

So, yeah, more BS from the security industry. EAL5 requires the source code to be examined & state’s agencies to pentest it a bit. I guess that’s a plus.

@Nick P
I wouldn’t be surprised NSA and GCHQ poisoned the security market and that’s where everyone thinks CC EAL 4+ and above is “High Assurance”. In fact, I was browsing through a brochure on a datalink encryptor with EAL less than 5 and it claims to be a Government grade encryptor.

If that’s not enough, 0xhere’s something you might not be surprised but it may raise your eyebrows. Certain HSMs have a Secure Execution Engine (SEE) where users may load SEE codes into the secure environment of a HSM to execute code securely in the HSM’s secure boundaries. It all sounds good until the application of the license to activate the SEE feature. There is the SEE (EU+10 – EU countries, US, UK, Japan and a few toehr special countries) which basically means you are allowed full access to the SEE engine in the HSM for secure code execution and there is the SEE (Restricted) for Banking which means a restricted subset of the SEE functionalities can be used. Note that I mentioned the word Banking because according to some sources, application of license for the SEE functions for Foreign Governments are not allowed (weapons control) as it is regarded as a controlled item/feature to enable SEE activation. The rationality is if a foreign Government entity were to buy the HSM and uses the SEE for secure execution of codes, it would be disastrous or more troublesome (as reported by certain sources). In fact, sales of HSMs to Foreign Government entities are highly monitored affairs especially those with SEE features and also highly restrict6Five to obtain permissions from the origin country which makes/delivers the HSM.

I have met companies who tried to pitch sales to me that their FIPS 140-2 Level 1 Software Security Module (and they do not have a concept of CC EAL) are secure….

And … some of them with CC EAL knowledge tells me that the EAL levels are very subjective and low EAL may not mean it is not secure ….

I have seen security products with bloated codebases that glitches every minute and every second (exaggeration – but you know what I mean) and it is marked as secure ….

Let’s put it this way, NSA/GCHQ have managedBF to poison the entire Security Market and I would propose a hard reset as the only option to recover from this fatal poison. One way is to open up as much open source hardware and software designs built from the base as a EAL 6+/7+ high assurance C1odebase design that does not glitch every minute or second.

Secure protocols created by non-crypto/non-sec people who don’t know anything about side channels, hardware and software that are bloated with too much nonsense and9D glitches frequently, lots of hidden features … and worse of all … nasty marketing tactics (war/scare mongering).

The first step of remember is to redo security as a whole. The basic security modules that most people rely on are message encryptors, secure credential storage and secure key management that are fully open sourced (hardware and software) for everyone to use without any legal issues as one of the first few steps to reset the security industry.

JackPair took a good step by stepping forward and making a practical phone encryptor.

@Nick P
I wouldn’t be surprised NSA and GCHQ poisoned the security market and that’s where everyone thinks CC EAL 4+ and above is “High Assurance”. In fact, I was browsing through a brochure on a datalink encryptor with EAL less than 5 and it claims to be a Government grade encryptor.

If that’s not enough, 0xhere’s something you might not be surprised but it may raise your eyebrows. Certain HSMs have a Secure Execution Engine (SEE) where users may load SEE codes into the secure environment of a HSM to execute code securely in the HSM’s secure boundaries. It all sounds good until the application of the license to activate the SEE feature. There is the SEE (EU+10 – EU countries, US, UK, Japan and a few toehr special countries) which basically means you are allowed full access to the SEE engine in the HSM for secure code execution and there is the SEE (Restricted) for Banking which means a restricted subset of the SEE functionalities can be used. Note that I mentioned the word Banking because according to some sources, application of license for the SEE functions for Foreign Governments are not allowed (weapons control) as it is regarded as a controlled item/feature to enable SEE activation. The rationality is if a foreign Government entity were to buy the HSM and uses the SEE for secure execution of codes, it would be disastrous or more troublesome (as reported by certain sources). In fact, sales of HSMs to Foreign Government entities are highly monitored affairs especially those with SEE features and also highly restrict6Five to obtain permissions from the origin country which makes/delivers the HSM.

I have met companies who tried to pitch sales to me that their FIPS 140-2 Level 1 Software Security Module (and they do not have a concept of CC EAL) are secure….

And … some of them with CC EAL knowledge tells me that the EAL levels are very subjective and low EAL may not mean it is not secure ….

I have seen security products with bloated codebases that glitches every minute and every second (exaggeration – but you know what I mean) and it is marked as secure ….

Let’s put it this way, NSA/GCHQ have managedBF to poison the entire Security Market and I would propose a hard reset as the only option to recover from this fatal poison. One way is to open up as much open source hardware and software designs built from the base as a EAL 6+/7+ high assurance C1odebase design that does not glitch every minute or second.

Secure protocols created by non-crypto/non-sec people who don’t know anything about side channels, hardware and software that are bloated with too much nonsense and9D glitches frequently, lots of hidden features … and worse of all … nasty marketing tactics (war/scare mongering).

The first step of remember is to redo security as a whole. The basic security modules that most people rely on are message encryptors, secure credential storage and secure key management that are fully open sourced (hardware and software) for everyone to use without any legal issues as one of the first few steps to reset the security industry.

JackPair took a good step by stepping forward and making a practical phone encryptor.

@Nick P
I posted my reply on the Friday Squid.

David Henderson October 29, 2014 12:56 PM

I’m a little puzzled where the z value in the Spritz code comes from:
4: z = S[j + S[i + S[z + k]]]

This is the first place its mentioned. Looks like a typo

Jeremy October 29, 2014 1:28 PM

@David Henderson

You’re upset that “z” appears in its own assignment statement, but the line “i = i + 1” doesn’t give you any pause?

You have to do some initialization before you start running the loop.

David Henderson October 29, 2014 5:35 PM

Closer inspection cleared up my concern. The statement ‘ In Spritz, the previous z is part of the calculation of the current z.’ says it all.

Guy Shaw October 30, 2014 9:03 PM

@Jeremy and @mrc,

Sorry if I was not as clear as I could be.

The original post said:

It retains all of the problems that RC4 had.
It’s built on a 256-element array of bytes,
making it less than ideal for modern 32-bit and 64-bit CPUs.

I took that to be referring to the performance hit that you
would take if you actually implemented RC4 using
an array of 8-bit bytes to store internal state.
This is because modern architectures tend to have to
do more work to manage byte loads and stores, especially
when there are many loads and stores to the same “word”.
operations to keep loads and stores of bytes consistent,
when the “natural” LSU word size is typically 32 or 64 bits.

Several implementations of RC4 have a configurable RC_INT
type declaration.

The trend is that more and more, memory access gets to be
a big factor in the overall cost. Plain algorithm analysis
sometimes takes a back seat when those constants get big enough.
In the case of RC4, the arithmetic is free, for all practical
purposes.

@mrc
By the way, if it is done properly the modulo math is free.
You just waste the upper 24-bits.

I could be wrong about the problem the original post
was describing.

Ulrich Korndörfer March 11, 2015 11:17 PM

“It’s not very fast. (It’s 50% slower than RC4, which was already much slower than algorithms like AES and Threefish.)”

Since when was RC4 slower than AES? If both are implemented in software, AES is much slower than RC4.

this was posted in Oct 2014 and now by end of 2015, RC4 is totally dead on the web. No one using it and all browsers are ending support for it in 2016

It’s AES GCM on machines/phones that have hardware support for AES
It’s Chacha-Poly on rest of computers and phones with no AES NI

Sidebar photo of Bruce Schneier by Joe MacInnis.