5
$\begingroup$

The inverse of Keccak is slow, but if you have a problem where that is not a concern would this be a secure cipher? The encryption function can be made incredibly fast in hardware. Or the reverse if you choose to encrypt using the inverse.

Is there any cryptanalysis of block ciphers that are unbalanced in such a fashion? Inverse being more expensive and having different diffusion properties.

The round constant step (used to break symmetry) in the round function is the only thing that needs to be changed to employ a key schedule.

The nonlinear step is worrisome, they use a simple cellular automaton rule: flip bit if pattern 01 is to its right (and wrap around). This makes invertability cumbersome for an arbitrary odd length input (not possible for even length), but they use it for just a 5 bit input which just makes it a trivial 2^5 S-box - is it a good one? 0* maps to 0* and 1* to 1* for example.

PS: * means repetition, in the case of keccak 1* = 11111

$\endgroup$
  • 1
    $\begingroup$ Note that for many common modes you don't actually need the inverse direction. $\endgroup$ – SEJPM Jan 15 '18 at 10:21
  • $\begingroup$ If you just want to use keccak for encryption, you could simply choose a suitable mode, no need to turn in into a block cipher. CTR, CFB and OFB should work with little change. Plus there is a sponge-like mode that offers authenticated encryption. $\endgroup$ – CodesInChaos Jan 15 '18 at 11:48
0
$\begingroup$

Yes.

I would first draw comparisons between an existing PRP like AES, that is known to be secure, and Keccak. The structure of Keccak and AES is very similar with the exception of some design choices as they fundamentally have different use cases, but regardless of their functional differences both are resistant against known cryptographic attacks. At their core they are both PRP’s, and support forward/inverse operations. Symmetric encryption is accomplished with AES by XORing an equal length KEY and MESSAGE. Keccak leverages state truncation to ensure that input recovery is impossible, and thus satisfies the standard hash function requirement of being non-invertible. To further demonstrate interoperability I would ask if AES could function as a hash digest, by leveraging state truncation, but the answer to that question is almost certainly no, without extensive algorithm modifications.

Now it’s necessary to demonstrate the similarities between the sub-functions that comprise both Keccak and AES. Below are the approximate complimentary functions between the two permutations.

$$AES \approx KECCAK$$

SubBytes() $\approx$ Chi():

['00000','00101','01011','01010',
 '10110','10111','10001','10100',
 '01101','01000','01110','01111',
 '00011','00010','01100','01001',
 '11010','11101','10011','10000',
 '11100','11111','11001','11110',
 '00110','00001','00111','00100',
 '11000','11011','10101','10010']

['00000','00001','00011','00010',
 '00110','00111','00101','00100',
 '01100','01101','01111','01110',
 '01010','01011','01001','01000',
 '11000','11001','11011','11010',
 '11110','11111','11101','11100',
 '10100','10101','10111','10110',
 '10010','10011','10001','10000']

This is where you correctly identified the 2^5 bit S-box in Keccak(), and with regard to your question about whether or not this is a good S-Box…I don’t know. If you were inclined to run this function with a look up table there would be design considerations that should be considered to ensure it runs in constant time, in my case I tried using Grey Code to mitigate these timing issues. Although if you’re going to live and die by Kerckhoff's Principle all cipher components must not only be public, but the most insecure cipher implementation must be used! Then consider banking systems, and understand that Kerckhoff's Principle is pure garbage.

ShiftRows() $\approx$ Rho()/Pi():

The two functions aren’t exactly the same since AES() is rotating bytes while Keccak() is rotating bits. Furthermore Keccak() acts on both columns and rows, while AES acts only on rows. But I think it's still an appropriate comparison.

MixColumns() $\approx$ Theta():

This comparison is a stretch, and is responsible for the performance difference that you referred to in your question. This also has the potential for adding security as it's the only function where tweaking Keccak() parameters might be safe. If I were to build a cipher out of Keccak() I would include a secret number of iterations of Theta() in the design. The NIST did this when they torpedoed the FIPS-202 specification by omitting the left circular rotation. Technically their test vectors don't match their algorithm specification, which is exactly what I would have done to protect myself in the event of a catastrophic break of SHA-3. But I can only speculate.

N/A $=$ Iota():

Now you mentioned in your question you would use Iota() to insert a key schedule into Keccak(). I would probably do something similar, but depends on if you're trying to build a symmetric or asymmetric encryption scheme. If I was building a symmetric encryption scheme with Keccak() I would generate one 1600 bit key and one 1536 bit key. Use the first for the initialization vector for Theta(), and the second to be inserted into Iota().

AddRoundKey() $=$ N/A:

Keccak() was not developed for symmetric encryption so it stands to reason there was no step for key insertion. Although the bird's method would probably work. See above or below:

$$E_k(m) = F(m \oplus k) \oplus k$$

Is there any cryptanalysis of block ciphers that are unbalanced in such a fashion?

Yes, any research completed on Theta() would meet this particular criteria. Although you may already have that link.

Source 1

Source 2

And my own testing:

def set_reduction(set_0,set_1):
    for i in range(len(set_0)):
        for x in range(len(set_1)):
            if set_0[i]==set_1[x]:
                return(True)
    return(False)

def CRYPTO_REDUCTION_FILTER(nested_lists):
    #A filter to be used in CRYPTO_REDUCTION() to structure the data for conclusion
    #processing. 
    to_return=[]
    for i in range(len(nested_lists)):
        insert=[]
        for x in range(len(nested_lists[i])):
            insert+=nested_lists[i][x]
        to_return.append(U_V(sorted(insert)))
    return(to_return)

def CRYPTO_REDUCTION(var_sets,bool_filter,direction_int): 
    to_return=[]
    while var_sets!=[]:
        insert=[]
        insert.append(var_sets.pop(direction_int))
        try:
            for i in range(len(var_sets)):
                if set_reduction(insert[direction_int],var_sets[i])==True:
                    insert.append(var_sets.pop(i))
        except IndexError:
            to_return.append(insert)
    if bool_filter==None:
        return(to_return)
    if bool_filter==True:
        return(CRYPTO_REDUCTION_FILTER(to_return))

def CRYPTO_REDUCTION_SECONDARY(var_sets,direction_int):
    to_return=[]
    while var_sets!=[]:
        to_check=var_sets[direction_int]
        insert=[]
        try:
            for i in range(1,len(var_sets)):
                if set_reduction(to_check,var_sets[i])==True:
                    if len(to_check) > len(var_sets[i]):
                        insert.append(to_check)
                        var_sets.pop(direction_int)
                        var_sets.pop(i)
                    if len(to_check) < len(var_sets[i]):
                        insert.append(var_sets[i])
                        var_sets.pop(direction_int)
                        var_sets.pop(i)
        except IndexError:
            None==None
        if insert==[]:
            to_return.append(to_check)
            var_sets.pop(direction_int)
        if insert!=[]:
            to_return.append(insert[direction_int])
    return(U_V(to_return))

def CRYPTO_DELTA_REDUCTION(var_sets,bool_filter,direction_int):
    to_return=[]
    while var_sets!=[]:
        insert=[]
        insert.append(var_sets.pop(direction_int))
        try:
            for i in range(len(var_sets)):
                if set_reduction(U_V(list_concat(insert[direction_int])),U_V(list_concat(var_sets[i])))==True:
                    insert.append(var_sets.pop(i))
        except IndexError:
            to_return.append(list_concat(insert))
    if bool_filter==None:
        return(to_return)
    if bool_filter==True:
        return(CRYPTO_REDUCTION_FILTER(to_return))

tl:dr

YES, because any other argument would require proving both AES and Keccak insecure. Don't use any of this for production code. If any of this answer is incorrect please make corrections.

$\endgroup$
  • $\begingroup$ "but regardless of their functional differences both have been proven secure" - you might want to unbox some of the details of this statement. Neither is provably secure in the sense of provable security - they demonstrate resistance against known attacks like standard linear/differential cryptanalysis, but that does not mean that breaking them necessarily implies the ability to break some "hard problem" (which is what "provably secure" typically means). $\endgroup$ – Ella Rose Jan 16 '18 at 1:15
  • $\begingroup$ So the presence of fixed points (0* and 1*) in an S-box is not a weakness of any kind? $\endgroup$ – user55068 Jan 16 '18 at 1:55
  • $\begingroup$ @dingrite Is this fixed point you're referring too in AES or Keccak? And could you edit you're question to indicated more specifically what the "*" means. $\endgroup$ – Q-Club Jan 16 '18 at 2:10
  • $\begingroup$ In keccak. * means repeated however many times, in the case of keccak, 5. $\endgroup$ – user55068 Jan 16 '18 at 3:35
  • $\begingroup$ @dingrite You keep changing your account! But I don't see why this would been an issue for the Keccak() hash application. However I have very little experience analyzing S-Boxs. $\endgroup$ – Q-Club Jan 17 '18 at 1:00
8
$\begingroup$

First, this is a slightly silly exercise because most applications are not well-served by a block cipher in particular but rather by things built out of them, such as authenticated encryption schemes. Probably the most widely used authenticated encryption scheme today built out of AES, AES-GCM, doesn't even use the inverse direction, and would provide better security bounds if AES were a pseudorandom function family rather than a pseudorandom permutation family. And there are already perfectly good authenticated encryption schemes built out of Keccak, such as Ketje and Keyak, both submitted to CAESAR.

But let's take the exercise at face value and suppose you really do want a block cipher. The obvious way to get a block cipher out of Keccak is with a single-key Even–Mansour construction analyzed by Dunkelman, Keller, and Shamir. Specifically, for a $b$-bit permutation $F$ (standard SHA-3 has $b = 1600$, but there are shorter variants, such as $b = 200$ used by Ketje for environments with tight resource constraints), we can define, for $b$-bit keys $k$, the $b$-bit block cipher $$E_k(m) = F(m \oplus k) \oplus k.$$ Since collision-resistance is not relevant to this application, instead of the standard $\operatorname{Keccak-\mathit{f}}[b] = \operatorname{Keccak-\mathit{p}}[b, n_r]$ permutation where $n_r = 12 + 2\log_2 (b/25)$ is the standard number of rounds, we might consider a much smaller number $n_r$ of rounds, as you will find Ketje and Keyak use.

Maybe a 1600-bit key seems excessive for a standard 128-bit security level. Maybe you could make do with a smaller key, padding it with zeros, $$E_k(m) = F(m \oplus (k \mathbin\Vert 0^{b - 256})) \oplus (k \mathbin\Vert 0^{b - 256}).$$ I haven't done the analysis of a padded-key variant of Even–Mansour; maybe if you read the Dunkelman, Keller, and Shamir paper you'll find an obvious answer. But we can always derive longer keys from shorter keys using standard functions like HKDF, or even Keccak-based ones like SHAKE256 or KMAC. So unless you have an amazingly constrained application requiring (a) squeezing out those last few cycles, and (b) a novel Keccak-based block cipher, those cycles are probably not worth the effort to figure out the detailed security analysis! Thus I leave it as an extra-credit exercise for the reader which will not affect your standard grade.

$\endgroup$
  • $\begingroup$ Derp. Evidently I once again neglected to read the question fully before shooting off an answer that went off into the weeds. Sorry! I'm going back into crypto.se rehab now until I can get my act together; maybe someone else can address the questions that were actually posed. $\endgroup$ – Squeamish Ossifrage Jan 15 '18 at 17:43
  • $\begingroup$ I'm not sure if you're being ironic but I found your answer very useful! As an addition, if performance is a concern, since Keccak was out there has been a few faster propositions (like Ascon: ascon.iaik.tugraz.at or Gimli: gimli.cr.yp.to) $\endgroup$ – Thomas Prest Jan 16 '18 at 12:46
  • $\begingroup$ @ThomasPrest Do you know where I might be able to find intermediate values for Gimli? $\endgroup$ – Q-Club Jan 17 '18 at 0:58
  • $\begingroup$ @colin we (the authors) provided an list of reference implementations of Gimli from C on different platform to Python 3. You can generate those intermediate values by yourself. $\endgroup$ – Biv Jan 17 '18 at 1:52
  • $\begingroup$ @Biv I literally have those implementations sitting on my computer! While the test vectors published in the gimli paper are helpful, the provided implementations don't handle the string conversions out of the box. Would you be willing to send me a single set of intermediate values? $\endgroup$ – Q-Club Jan 17 '18 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy