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

Russell Leidich pkejjy at gmail.com
Thu Dec 27 09:22:44 EST 2012


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^50 (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. I look forward to the cracking competition...

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?

Russell Leidich

On Thu, Dec 27, 2012 at 1:26 PM, Ben Laurie <ben at links.org> wrote:

> On Wed, Dec 26, 2012 at 9:38 PM, Jon Callas <jon at callas.org> wrote:
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA1
> >
> > I took a look at it. Amusing. I didn't spend a lot of time on it.
> Probably not more than twice what it took me to write this.
> >
> > 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.
>
> It is not self-evident how you might go about this, and, indeed, their
> own analysis rests on the difficulty of doing it, so "since the
> tumbler is just a big bitstring, work from there to pull out the whole
> thing" hardly cuts it as a viable attack.
>
> Much as I am inclined to suspect this scheme doesn't work, you've shed
> no more light that their own paper does.
> _______________________________________________
> cryptography mailing list
> cryptography at randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20121227/c73ffbc3/attachment.html>


More information about the cryptography mailing list