Re: [Cfrg] Crystalline Cipher

"Mark McCarron" <mark.mccarron@eclipso.eu> Sat, 23 May 2015 02:01 UTC

Return-Path: <mark.mccarron@eclipso.eu>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8F1061A8AB8 for <cfrg@ietfa.amsl.com>; Fri, 22 May 2015 19:01:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.928
X-Spam-Level:
X-Spam-Status: No, score=-0.928 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, GB_I_LETTER=-2, HELO_EQ_DE=0.35, HTML_MESSAGE=0.001, MIME_HTML_ONLY=0.723, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VBOBpJXyrH3x for <cfrg@ietfa.amsl.com>; Fri, 22 May 2015 19:01:41 -0700 (PDT)
Received: from mail.eclipso.de (mail.eclipso.de [217.69.254.104]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 77D671A8A85 for <cfrg@irtf.org>; Fri, 22 May 2015 18:56:56 -0700 (PDT)
Received: from mail.eclipso.de (www1.eclipso.de [217.69.254.102]) by mail.eclipso.de with ESMTP id 40811ADB for <cfrg@irtf.org>; Sat, 23 May 2015 03:56:54 +0200 (CEST)
Date: Sat, 23 May 2015 03:56:53 +0200
MIME-Version: 1.0
Message-ID: <05817743fc3a9062d8952ba25c09f84d@mail.eclipso.de>
X-Mailer: eclipso.eu/7.3.0
X-Sender-IP: 81.152.140.34
From: Mark McCarron <mark.mccarron@eclipso.eu>
To: Tony Arcieri <bascule@gmail.com>
In-Reply-To: <CAHOTMVKVX=K68fuS1tq0kAWV3AAxERM+PCT-ar_hJkKorquR5A@mail.gmail.com>
References: <8e7ec9ae7082fac7061fe60faaa00106@mail.eclipso.de> <555DF1B7.4010500@shiftleft.org> <b5451ad486d461a38a6d19655322cfd3@mail.eclipso.de> <264518D0-89EE-427C-B011-B1582B9C98E2@shiftleft.org> <aa8324752ab4c6ec26650852318766f4@mail.eclipso.de> <555E4524.2060600@gmail.com> <fcb97b7182d9c0e306fd72a5f7e97959@mail.eclipso.de> <8e9abc468e6f49d4b576515c401c6d20@ustx2ex-dag1mb2.msg.corp.akamai.com> <dcf257ea9d53bca2d492e8af8af3cf97@mail.eclipso.de> <CAHOTMVKVX=K68fuS1tq0kAWV3AAxERM+PCT-ar_hJkKorquR5A@mail.gmail.com>
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/Uum-O2gHX2iA_Hc4RhyiSd9W-Xo>
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Crystalline Cipher
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
Reply-To: Mark McCarron <mark.mccarron@eclipso.eu>
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sat, 23 May 2015 02:01:45 -0000

Hi Tony,

This is a bit of moot point as I am introducing changes that will correct this.  But, I will address this issue as there is a fundemental difference between RC4 and Crystalline.  This difference means that a bias in the output, does not lead to a break in the cipher.  Let me explain this.

I would think of the break in Enigma in slightly different terms.  The fact that a key never encoded itself, provided a point of reference from which to begin a process of elimination that reduced the number of permutations to a level that could be feasibily be computed in a short period of time.

In RC4, as far as I am aware, the break was of a different nature.  A small, but detectable bias, effectively modulated data that could be recovered statistically.

In Crystalline, the bias that is observed in each output is generally unique.  Operator error can cause issues, but that is true with all ciphers.  The ciphertext is a product of the XOR, the original plaintext and random input.  As the cipher passes through the file serially, it swaps the bit from the current index (whilst XORing it with true) with a randomly selected bit between 0 and 65535 locations away, alternating the direction with each increment.  It repeats this for every bit in the file.  It then passes through the file serially again performing a similar swap of the bytes only without an XOR.  This process is defined as a round and at minimum 10 rounds are applied.  The effect of this the bits of any given byte from the original plaintext can be anywhere in the file and can be any state (1 or 0). 

It is like throwing a hand grenade at the data.  There is no mathematical relationship between the location of the bits, so no formula, however complex, can be applied to recover the data.  The only practical approach is to seek patterns that can identify the key.  The issue is that the patterns of the final cipher text, do not map up in any way to the original key, they map to the previous layer and the layer before that and so forth.  In certain plaintexts such as a file filled with 0x00 you can observe some patterns when presented in images, but this as an echo of a signal that has degraded beyond the point of recovery. 

So, the cipher is much more complex than a cursory examination would suggest and issues that are big things in modern ciphers, are not serious issues for a cipher such as Crystalline. The principles are different, thus the attack vectors are different.  It probably has more in common with analogue signal recovery than it does with traditional cipher breaking.

As for being indistinguishable from noise, this is one way of achieving security, it is by no means the only method.  Simply making information unrecoverable (which is defined as information loss in the context of Crystalline) will achieve the same effect.  It is similar to a 'minimum detectable signal' in radio engineering.  I hope you can see that both techniques are doing the same thing, only they do it in different ways.  So, bias is not the enemy of Cryptography (at least not Crystalline), the enemy is points of reference (as in the Enigma break) which can be related to other information to enable feasible computation.

It somewhat surprises me that this knowledge appears to have been lost at some point in the Cryptographic community.  Perhaps it is a product of the move to digital technologies.

Regards,

Mark McCarron




--- original message ---
From: Tony Arcieri <bascule@gmail.com>
Date: 23.05.2015 00:32:36
To: Mark McCarron <mark.mccarron@eclipso.eu>
Subject: Re: [Cfrg] Crystalline Cipher

On Fri, May 22, 2015 at 1:02 PM, Mark McCarron <mark.mccarron@eclipso.eu> wrote:
To understand the principles behind Crystalline, I would recommend brushing up on Lorenz and Enigma.
 
Hi Mark,
 
I'm quite familiar with Lorenz and Enigma, both of which are considered extremely broken today.
 
Enigma contained a bias because it never mapped a letter to itself. Any such bias is sufficient to break a cipher.
 
Your cipher is full of similar biases:
 
 
If it were a good cipher, it'd appear flatter:
 
 
Note that RC4 is not a good cipher. You may not know it, but Kenny was part of a team that found such biases in RC4.
 
Your cipher has biases. Therefore it's broken. Period. I know you disagree, but you're wrong. Period. Your cipher is broken. End of story.
 
By modern standards, your cipher should be indistinguishable from random data even in the presence of a chosen ciphertext attack, something I'm fairly certain you're not even familiar with:
 
 
Your cipher is obviously distinguishable from random data, simply by looking at an image of the ciphertext:
 
 
If you have a genuine interest in cryptography, I hope you take these things to heart, study them, and improve your knowledge of cryptography.

---
Free, fast and secure email: https://www.eclipso.eu" rel="nofollow">https://www.eclipso.eu