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 <[email protected]> wrote: > On Wed, Dec 26, 2012 at 9:38 PM, Jon Callas <[email protected]> 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 > [email protected] > http://lists.randombit.net/mailman/listinfo/cryptography >
_______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
