[cryptography] Tigerspike claims world first with Karacell for mobile security

Russell Leidich pkejjy at gmail.com
Thu Dec 27 04:18:29 EST 2012


Hi everyone. This is the Karacell team at Tigerspike. This thread has been
brought to our attention (thank you, Anonymous) and we'd be happy to
address various concerns, which we've done in detail below, for starters.
I'm Russell Leidich. Stuart Christmas would like to start off by saying:

-----------------------------------------------------
This is a response from the principle engineer and secondary engineer on
the Karacell system you have been discussing. First, we would have to agree
with you all on the marketing "fluff" - sadly that's a necessary evil these
days when science and business merge. However, we feel the fundamental
principles behind the press release are valid, albeit dredged through the
marketing machine first (the term "Military-Grade encryption" makes me
cringe too, but sometime you have to pick your battles)....

However, one goal of such a press release is to get a more sensible
scientific conversation started, so I guess it's been a success in that
regard at least. I was particularly interested in the comments from Jon. It
seems we didn't explain a lot things clearly enough in the paper, which has
lead to some misunderstandings.
-----------------------------------------------------

Russell again. We will soon be posting a "Karacell challenge" with prize
money to anyone who can crack a short test file. More on that below.

Secondly, we've received a lot of criticism of this algo. 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 complaints. 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 the prize money. 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
1Q2013, such that the prize is announced after the source code has been
published along with a new reference document.

Furthermore, I might add, it's in our interest to increase the prize money
as time goes by. We'll say more through public press release channels next
quarter.

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^50) in order to generate the tumbler sets.

2. The algo 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/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
issues that you all have brought up, in no particular order. I'll put a "Q"
next to your 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^64 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
modificationp; 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.) 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 roughly the square as long.

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.

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. He invented his 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 algo,
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 algo, 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 algo. Karacell makes this difficult simply
due to the number of qubits required for temporary storage, which is
probably 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 algo using the
knapsack problem (loosely related to Sumset Sum) that was proven weak years
ago. Karacell is a totally different algo (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.

Russell Leidich
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20121227/1833aa5a/attachment.html>


More information about the cryptography mailing list