Karacell

Karacell is Tigerspike’s revolutionary encryption system designed specifically for (but not restricted to) mobile applications. It boasts the following:

  • Entirely bitwise parallel, meaning its not only faster than anything out there today, but will scale exponentially with advances in technology.
  • Resistant to attacks by quantum computer.
  • Based on solid provable mathematics and known NP-Complete computation problems – meaning it’s provably stronger than anything else.
  • Extremely low power consumption to preserve battery life in mobile devices.
  • Low footprint so as not to interefere with the device it’s being used on.
  • All cryption can happen in physically secure memory (such as the L1 cache) avoiding all sorts of side-channel attacks.
  • Has a mathematically provable limit cycle in the order of 10^100.
  • Has an astonishingly secure and proprietary cryptographic hash baked right into the algorithm (see the LMD Hash Family section of this blog).
  • Uses a unique TRNG for generation of the initial value (IV). (See the Jytter section of this blog).

This page is dedicated to discussions concerning Karacell.

The whitepaper with description and algorithm can be found here.

5 responses

10 01 2013
stuxmas

So, received a lot of comments on this algorithm. That’s unsurprising, since no cryptographer has ever made a name for themselves by saying “I think this is secure.” But it’s also valuable, because it’s allowed us to ascertain the elements of the design that should be improved.

We have received, above all, 2 very common comments. Both of these are being addressed in the upcoming release of Karacell 3. (Karacell 2 was an internal experiment.) That’s around the time that you can expect to see a press release with the details of how to claim prize money for cracking a test file. We also intend to have a source code release at that time, so you all can have a look at the implementation. It’s our intention to have all this done within 2Q2013, such that the prize is announced after the source code has been published along with a new reference document.

So in particular, these 2 most popular complaints are as follows:

1. We don’t trust that the limit cycle of the oscillator which forms the xor masks is long enough to be secure.

To this end, we’ve done our own internal analysis, using extrapolations from “mini Karacell” implementations, in order to see how the histogram of limit cycles scales. Nonetheless, we’ve realized that people want mathematical proof. OK fine. Karacell 3 will use a different oscillator of known period (in excess of 10^100) in order to generate the tumbler sets.

2. The algorithm is too complicated. And what’s this “combinatorial decomposition” thing all about?

OK got it. Karacell 3 will be simpler and not involve combinatorial decomposition. It will also more tightly reflect the Subset Sum NP problem. (Technically, solving Subset Sum involves only answering a yes/no question, whereas Karacell 1,2 and 3 requires specific identification of the xorends/addends, but this is a minor distinction in terms of computational complexity.)

So, having said that, Karacell 3 is still Subset Sum at heart. If you can find out how to crack a Karacell 3 file without solving Subset Sum, then by all means keep an eye out for the upcoming competition, and claim the prize money.

Now for the benefit of posters and lurkers, let’s go through some of the specific issues that you all have brought up, in no particular order. I’ll put a “Q” next to the issue, and an “A” next to our reply.

Q. It has an obvious problem with known plaintext. You can work backward from known plaintext to get a piece of their “tumbler” and since the tumbler is just a big bitstring, work from there to pull out the whole thing.

A. That would work if there were only 1 tumbler. But in its weakest incarnation (128-bit key), there are 24 tumblers, which each select a different rotations of a string 2^16 bits long (the “Karacell Table”), which are then all xored (or modulo-2^N added with carry propagation, in Karacell 3) together.

Q. The encrypted Karacell file format has 64 bits that must decrypt to zero. Since encryption is an XOR onto a pseudo-one-time-pad, this leaks 64 bits of the tumbler.

A. Karacell was designed on the assumption that the entire plaintext is 0, i.e. the attacker knows all of the xor masks that were used to encrypt the file. What you see in this 64 bits (must_decrypt_to_zero) is a 64-bit slice of the xor of many rotations of the Karacell Table. So yes, we’re “leaking” the sum of the subset. But that’s what your given as input to the Subset Sum problem. So it’s not useful information, in and of itself. This field is merely intended as a quick check as to whether the key is valid, and is iteratively distant from other xor masks used elsewhere. In effect, you can think of it as the first packet (even though it’s too short to be a full packet).

Q. Similarly, the “checksum” at the end is a bunch of hash blocks of their special hash all XORed together. This doesn’t work against malicious modification; you can cut-and-paste through XOR, etc.

A. You can only cut-and-paste through a xor mask if you know what the mask is. But in order to know the mask, you need to know the tumblers. And in order to know the tumblers, you need to solve Subset Sum for the part of the mask which was xored to the plaintext. Specifically, if you know the entire plaintext, and thus the xor mask, then you need to solve Subset Sum. If not, then the problem is only harder. Put another way, without doing the foregoing, you don’t seem to have any clue what the pseudorandom seeds are which were fed into the hash, so you can’t compensate it for your malicious modification. Plus, the hash is then encrypted with Karacell itself.

Q. There are obvious vulnerabilities to linear and differential cryptanalysis.

A. Such as?

Q. It is a lot of XORing on large-ish fixed longterm secrets with only bit-rotating through the secrets, and between the vulnerabilities of known plaintext as well as the leaks in it, I don’t see a lot of long-term strength. I bet that you can use known structure of plaintext (like that it’s ASCII/UTF8, let alone things like known headers on XML files) to start prying bits out of the tumblers and you just work backwards.

A. If you reuse the same xor mask twice, anywhere in the world, then you have some useful information about the mask, because most bits in the world are 0. (This is of questionable utility when most of the traffic in the world is compressed, i.e. high-entropy, but let’s assume that all packets everywhere are 0, just to make life hard on us and easy for a potential hacker; ie, assume the worst case for us.) Our estimate, based on limit cycle histogram extrapolation (i.e. the expected value, not the maximum value), is that Karacell 1 reuses the same xor mask once in every 10^27 packets, given the same 128-bit master key (to say nothing of 512-bit keys). We could refine this rough number, but it’s a moot point. Karacell 3 will use a known-limit-cycle oscillator of about 10^100, so we’re not losing sleep on that one.

Q. But beyond that, it isn’t even particularly fast. Since it needs a lot of bit extraction and rotations, I doubt it would be as fast as AES on a processor with AES-NI instructions. The whole thing is based on doing 16-bit calculations and some bit sliding; I don’t expect it to be as fast as RC4 or some of the fast estream ciphers.

A. AES uses 128-bit blocks. Karacell uses 32768-bit blocks. Many people are quick to point out that Counter Mode AES can process many blocks in parallel and in advance of plaintext arriving, in the sense of precomputed xor masks (just like Karacell), but there are plenty of Googleable papers showing the Counter Mode is weak relative to (conventional) cipher-block-chaining (CBC) AES. What we’re comparing is CBC AES to Karacell, assuming “very wide” SIMD. In this case (and granted, it might take a GPU with wide SIMD and memory bandwidth) Karacell would fry AES. But yes, if you’re talking a 386 CPU from 1990, then Karacell would lose. Thankfully we’re designing for the present and future, not the distant past.

Q. Obviously, I could be missing something, but there are other errors of art that lead me to think there isn’t a lot here. For example, if your basic encryption system is to take a one-time-pad and try to expand that out to more uses, zero constants are errors of art. You should know better. There are similar errors like easily deducible parameters that give more known plaintext. The author discusses using a text string directly as a key, which is very bad with his expansion system.

A. I addressed the zero constant above. Using a text string as a key presumes that the string is a fully entropic hexadecimal key — not some English word.

Q. They invented their own “message digest” functions, and they look like complete linear functions to me. They’re in uncommented C that’s light on indenting and whitespace. Confirmation bias might be making me miss something, but it’s not like he made it easy for me.

I believe you’re referring to:

http://leidich-message-digest.blogspot.com/2012/04/the-lmd4-lmd5-and-lmd6-secure-hashes.html

The little snippet down several paragraphs from the top shows the algorithm, which is directly (albeit somewhat obscurely) reflected in the C code. Correctness was verified using a large integer calculator.

The functions are not linear. They resist second-preimage attacks in the sense that they use the xor (effectively) of 2 oscillators of known and prime period, half a packet apart. So the “last” word in an 2N-word packet is both the Nth word and the 2Nth word to be integrated into the hash, i.e. one component of the xored subhashes has undergone at least N iterations by the time the hash is issued, regardless of which word we’re talking about. You can think of it as 2 nonlinear (and in practice, unbiased) oscillators of different and prime periods being destructively xored together, while being integrated with the plaintext at every iteration. The seeds to the hash are supplied by Karacell (essentially, “off the end” of the xor mask, i.e. opaque even in the event that the plaintext is all 0s). The hash itself (LMD6 in Karacell 1) is then encrypted. This last step is unnecessary as far as I can see, but it’s cheap and makes things harder, so why not.

As to the uncommented C code, I apologise. It was largely computer-generated code, and I was too lazy to fill in the comments after debugging it. If people are interested in attacking the algorithm, then I would be compelled to release a more commented version. (Note that LMD is my stuff, but Karacell belongs to Tigerspike.)

Q. My understanding was that there was a general quantum algorithm for brute force in 2^sqrt(keylen). The real threat is to public key algorithms.

A. At best, as far as I understand, a quantum computer can indeed root the complexity of (any) classical algorithm. Karacell makes this difficult simply due to the number of qubits required for temporary storage, which is easily 2+ orders of magnitude higher than AES, mainly on account of the true random Karacell Table. (AES does use a (much smaller) lookup table as well, but it’s “special” (Galois groups, if I recall) and could thus probably be generated in some way that requires much less storage than storing the whole table.) I’m not sure I would characterize them as being a bigger threat to public key (asymmetric) than symmetric algos. They’re a major problem for both, if the engineers can make them work.

Q. I’ve never heard that allegation [bitwise anisotropic encryption strength] against AES. I am confident that had it been known way back when, Rijndael never would have been selected.

A. While this isn’t really material in terms of Karacell vs. AES (because Karacell is isotropic by design, on account of not depending on the plaintext for strength), I do think this is the case for AES, assuming cipher-block-chaining, because then you’re dependent on plaintext complexity for cryptographic strength. This doesn’t mean that AES is easy to crack. It just means that some bits are more strongly encryped than others.

Q. Remember trapdoor knapsacks? The issue isn’t the *worst case* complexity for solution, it’s what a cryptanalyst would typically encounter.

A. Perhaps you’re referring to the asymmetric encryption algorithm using the knapsack problem (loosely related to Sumset Sum) that was proven weak years ago. Karacell is a totally different algorithm (and symmetric). And yes, we look at statistically expected cases, as best we can approximate them, not the worst case.

That’s all for now, and thanks everyone for your feedback.

10 01 2013
stuxmas

There have also been a number of posts and comments on our reliance on the Subset Sum Problem. Here is a boilerplate concern along with a more detailed answer, with a footnote on malicious hash modification.
Q: It has an obvious problem with known plaintext. You can work backward from known plaintext to get a piece of their “tumbler” and since the tumbler is just a big bitstring, work from there to pull out the whole thing.
A: Yes, you can work backward from a known xor mask (due to a known plaintext) to the master key. You just have to solve the Subset Sum problem several times, serially:

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

In particular as applies to Karacell, the Horowitz and Sahni approach (essentially, meet-in-the-middle, and big-O analyzed toward the end of our paper) would appear to be the fastest of the choices presented in the above article. What you’re looking for is the particular rotations of the Karacell Table which were xored (Karacell 1) or added (Karacell 3 …soon) together to produce the “sum”, which is then used as a xor mask for encryption. Subset Sum is NP-complete, but don’t let that stop you. Perhaps there’s a way to use the tumblers for block N to learn something about the tumblers for block N+1. The tumblers for block N+1 are generated, in fact, from the tumblers from block N, using the same Subset Sum process (essentially, from continuing beyond the point where the xor mask is issued, into opaque territory which is not used for encryption). (In Karacell 3, tumblers will be generated from a known-limit-cycle chaotic oscillator with no meaningful bit lane bias. But nevermind. Attacks on Karacell 1 are equally welcome here.) Either way, you need to use the xor masks (assuming 100% known plaintext) to help you find the tumblers used to encrypt block N, then work this all the way to block 0’s tumblers, and from there to the master key. (Block N here is the earliest block for which you know a “useful” amount of the xor mask.)

Alternatively, you can generate 10^27 (Karacell 1 with 128-bit key) or something over 10^100 (Karacell 3) xor masks, give or take. (Obviously if the key is easier to crack via Horowitz and Sahni than generating so many xor masks, then you would do that instead.) One of them will probably be identical to the one that you’re trying to crack, and know only part of. When you see a fragment of a generated mask which matches a fragment that you know in the mask you’re trying to crack, you can try using the generated mask and see if it works, thereby revealing the rest of the packet. If it does, then you’ve compromised a packet (congrats!) but still know nothing about the master key. By the way, there are many different limit cycles in Karacell. So all this assumes that you happen to be on the same limit cycle as the person who encrypted the file. That’s actually very improbable because you don’t know the master key and probably didn’t happen to guess another key which happens to live on the same limit cycle. But we didn’t bother to compute exactly _how_ improbable (something less than the estimated 1 in 10^27, on average), because we decided to change to a proven oscillator in order to moot the whole discussion of limit cycles.

If anyone can crack Karacell without Subset Sum then they’re a hero, to say nothing of how cool it would be if one could show Subset Sum to be a polynomial time problem.

Please note, Subset Sum is related to various knapsack problems. Some knapsack problems are linear time. Subset Sum, however, does not appear to be. So there’s no need to knee jerk into “xor = weak” or “knapsack = cracked”. Not that anyone did that. Just for the lurkers.

By the way, regarding malicious hash compensation, I said “You can only cut-and-paste through a xor mask if you know what the mask is.” This is nonsense (not enough coffee today, sorry). What I was trying to say is best expressed mathematically:

1. We have (M xor H0) at the end of the file, where M is some xor mask generated for the sake of encryption, and H0 is the LMD6 hash of the original file.

2. You want to change this to (M xor H1), in order to compensate for your malicious changes. So you just need to know (H0 xor H1).

3. You know neither H0 (because it’s encrypted) nor H1 (because you don’t know what seeds to feed into LMD6 hash, which depend on the master key). Now what?

10 01 2013
stuxmas

These are responses to a journalist in an interview-like setting. We have responded in such a way that we hope the nature of the question is implied in the context of the answer.

As to where the industry is going, we can see a complexity implosion catastrophe on the distant horizon, perhaps a few decades away (which is increasingly relevant to present encryption requirements). Let us explain what we mean by that.

At present, unlike prime factorization as pertains to RSA, no one has found a way to accelerate the Subset Sum problem on a (theoretical) quantum computer. To the extent that one must solve such a problem in order to crack Karacell (which is required), this implies that RSA stands to suffer from up-to-square-root-factor acceleration relative to Karacell at the same key length, should such a quantum computer be built. This amounts to an implosion of computational complexity, and it’s most definitely a catastrophe! As time goes on, we think people will start to realize that quantum computing, if not inevitable, is a major risk card in the deck. The safe option is to use an algorithm which does not benefit from quantum acceleration. And by the way, the number of qubits (quantum bits) required to implement Karacell cracking on a quantum computer is 1 or 2 orders of magnitude higher than for AES, on account of Karacell’s deliberately obnoxious temporary memory space requirements. In everyday terms, that’s easily another decade of Moore’s Law. The same logic applies to classical attacks: one would need 10-100X as much power to attack the same key length of Karacell, vs. AES, because Karacell intentionally uses so many transistors on memory requirements, that otherwise could have been used for cracking operations.

As to RSA key elimination, we believe you’re referring to the fact that we still need to do a key exchange, in order to initialize a channel which forever after may use (symmetric) Karacell encryption. In this case, (1) a meeting in the park is always the best option and (2) if that’s not feasible, then one must use sufficiently long RSA keys so that the expected quantum computer cracking time (Shore’s algorithm most likely) is in excess of the estimated Karacell cracking time (which is not too difficult to estimate, given a specific key length). Yes, this means that RSA might be very slow, but we’re only talking about exchanging hundreds of bits one time per pair of peers, so it’s negligible (unlike using RSA for file transfers of any useful size).

As to getting Karacell to the masses, that’s an awareness problem. At some point, there may be a complexity implosion catastrophe of the sort described above (or involving some other exotic form of computer). Were that to occur, lots of people and documents would become naked overnight. We realize that this all sounds like science fiction, but then, 56-bit keys were all the rage in 1970. By migrating to a safer algorithm today, we can buy ourselves an insurance policy. With Karacell, the underlying math problem has been sitting around unoptimized since 1972. It will take time for the industry to admit to the real risks of the current state of the art. People need to make progress in strength per key bit because Moore’s Law isn’t taking a vacation, and human memory isn’t getting any better.

“Isolated trust” is absolutely #1 on our list of target applications. Especially where low latency is a must, for instance, medical implants, automotive subsystems, and private fiber.

As to being designed for parallel computing, we’re not really commenting on strength when we talk about parallelism, which was covered above, the parallel nature is all about speed. What we’re talking about is that Karacell (and Karacell 3) are designed to map efficiently to very wide SIMD architectures, of the sort one might find in a modern GPU. A Karacell packet is 4K bytes wide, and the algorithm is packetwise serialized. Except for some carry propagation in Karacell 3, which can be hidden in memory latency for the most part, Karacell is fully bitwise parallel across this entire width. AES, by contrast, is only 128 bits wide. Now, on a generic 64-bit CPU with AES acceleration instructions, one will find that AES is faster. But going forward to the GPU era, Karacell has scalability where AES does not. It has been pointed out that so-called “Counter Mode” AES is very parallel, so that in principle one could perform encryption with unlimited width. However, the Internet is replete with whitepapers discussing exactly how to initialize the pseudorandom seeds for this process, which invites a minefield of cautionary notes. There are also many whitepapers stating categorically that AES counter mode is flat out weak (which is actually semi-obvious when you look at the scheme in the first place). Given the choice, personally, we would rather stick with “conventional” AES, which is serialized on 128-bit chunks. At least you know you’re safer. But then performance goes down the drain, so the option then is Karacell.

As to SHA-3, that’s a cryptographic hash, whereas Karacell is an encryption algorithm, so they’re quite different. However, Karacell does incorporate an encrypted LMD6 hash, which serves a purpose analagous to SHA-3, albeit in a stronger sense as we use the same maths that underlies Karacell with a provably long limit cycle. We plan to release Karacell 3 reference code in 2Q2013, along with a public cracking contest.

10 01 2013
stuxmas

The following comments are to a professor and his Masters student writing a dissertation on methods of testing new encryption algorithms. As with the last post, we have structured the answers so the nature of the question is implicit (at least that was our goal). They pertain mostly to the speed tests we ran, which was basically a contest of “is the XOR operation faster than the entire AES algo” which of course it is by a factor of god know what, once we pre-compute the cryption mask, which we can also do faster than AES throughput. Then it goes on to the same story of quantum cracking.

As to benchmark tests, we’ve done them, and we beat AES, but we didn’t optimize either system to the hilt, primarily because modern processors include AES acceleration instructions, but not of course Karacell acceleration instructions; on the other hand, our Karacell code is multithreaded C, and the AES code was C++. We also had different IO access patterns to the test file. Specifically, all we really need is a very wide SIMD pipe with ‘add’ and ‘xor’ functionality. If we had that, then at 32K bits per block vs. 128 with AES, we absolutely SMOKE AES, hands down, because of the parallel nature of Karacell. (GPUs offer some useful facilities in this regard. We would prefer to optimize for the future, than the past. However, we don’t have a GPU version at the moment, which is nonetheless easily constructed.) There are some folks who point out that AES counter mode can allow it to become an arbitrarily parallel algo. I’m not convinced, because there are several whitepapers out there pointing out the weaknesses in counter mode. So then we’re back to “conventional” cipher block chained AES, which is slow and suffers from susceptibility to chosen plaintext attack, to which Karacell is immune by design. Personally, if I had to use AES, then I’d rather use the mode which has received fewer safety concerns, which is the chained version.
Karacell is also precomputable in the absence of any plaintext (because you can just xor on the precomputed xor masks later, at trivial cost), whereas plaintext-chained AES is not. So our latency is basically as long as it takes you to xor a packet (4K bytes).

They key point to note here is that we incur a small penalty in pre-computing a cryption mask, which we argue can be done whilst the user is dialing (in the case of an encrypted voice call) or initiating a video connection when video conferencing, or whatever. Then the cryption speed is as fast as your hardware can load blocks and XOR them together, which is astonishingly fast. If and when you start to run out of cryption mask, you divert some computing power to generating more, and this can be done with as much built-in intelligence as you deem necessary.
However, in the tests we ran, our pre-compute speed is still faster than AES encryption speed, even with adding the step XOR’ing to the plaintext to perform the encryption. And that’s not mentioning the fact that we have a built in state-of-the-art cryptographic hash baked right into the algo, where as AES does not.

So for the tests, we did head-to-head with moderately optimized algos in C++, and beat AES by around 10-20%, which does not involve precomputation. When we allowed precomputation of the cryption mask (which we can churn out 2GB worth in about 11 seconds on an old cheap laptop), then we are basically comparing AES with how fast our 5-core machine can perform parallel XOR, so yeah we wiped the floor with them. We didn’t go into predicting when the cryption mask would run out and diverting some core(s) to generating more, but that’s still moot when you compare the speed of the basic XOR operation with the speed of AES. It’s just no contest. Some people argue we can’t start the timing clock when we’re pre-computing because AES has to wait for plaintext before it can start, so it’s not fair. We say “boo-hoo”, cry to someone else because we found a way to reliably pre-generate cryption masks with staggeringly long limit cycles, so deal with it!

As to cracking, there is no quantum computer in existence which can crack AES with a 128-bit key, and probably no classical computer, either. But we’ve designed Karacell with the assumption that this statement will be false within a human lifetime, and possibly within a decade. The key difference with this argument is not so much speed. It’s strength per key bit. Karacell cannot be accelerated on a quantum computer, even if you had one with enough qubits (O(100K)). This is because there hasn’t yet been any success in the quest to accelerate the Subset Sum problem on a theoretical quantum computer. So that means AES gets up-to-root-factor acceleration, and Karacell gets no acceleration at all. Which means, if you have a general purpose quantum computer with enough qubits (O(10K)) to crack AES, then your 128-bit AES key is worth something like a 64-bit Karacell key. But even then, not quite, because Karacell’s “hot” temporary memory footprint is 10X or 100X as large. Which means that you have only 1-10% as much computational throughput, because you need to devote logic elements to memory that could otherwise have been used for computation. This kind of advantage is easily a decade of Moore’s Law advantage in terms of expected privacy duration with Karacell.

As to connection errors, Karacell doesn’t do anything. A higher level in the communication stack would simply resend the lost packet, or cover for it with an error correction code. We do, however, implement it with an encrypted LMD6 hash, to protect against malicious modification. If you think we’re missing something in this regard, then we’re happy to listen.

14 02 2013
Using cars and technology to kill people « Luke Janssen

[…] we have a solution to this issue at least – read here if you are […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: