*12:17* [Pub][ePrint]
Explicit Non-Malleable Codes Resistant to Permutations, by Shashank Agrawal and Divya Gupta and Hemanta K. Maji and Omkant Pandey and Manoj Prabhakaran
The notion of non-malleable codes was introduced as a relaxation of standard error-correction and error-detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value.In the information theoretic setting, although existence of such codes for various rich classes of tampering functions is known, explicit constructions exist only for highly structured family of tampering functions. Prior explicit constructions of non-malleable codes rely on the ``compartmentalized\'\' structure of the tampering function, i.e. the codeword is partitioned into {\\em a priori fixed} blocks and each block can {\\em only} be tampered independently. The prominent examples of this model are the family of bit-wise independent tampering functions and the split-state

model.

We consider an infinitely large natural class of non-compartmentalized tampering functions. In our model, the tampering function can permute the bits of the encoding and (optionally) perturb them. In the information theoretic setting, we provide an {\\em explicit} and {\\em efficient}, {\\em rate-1} non-malleable code for {\\em multi-bit messages}.

Lack of explicit constructions of non-malleable codes for non-compartmentalized tampering functions severely inhibits their utility in cryptographic protocols. As a motivation for our construction, we show an application of non-malleable codes to cryptographic protocols. In an idealized setting, we show how string commitments can be based on one-bit commitments, if non-malleable codes exist. Further, as an example of a non-trivial use of non-malleable codes in standard cryptographic protocols (not in an idealized model), we show that if explicit non-malleable codes are obtained for a slightly larger class of tampering functions than we currently handle, one can obtain a very simple non-malleable commitment scheme, under somewhat strong assumptions.

*12:17* [Pub][ePrint]
Analysis of NORX, by Philipp Jovanovic and Samuel Neves and Jean-Philippe Aumasson
This paper presents a thorough security analysis of the AEAD scheme NORX,focussing on differential and rotational properties of the core permutation.

To examine its differential properties, we first introduce mathematical models

that describe differential propagation with respect to the non-linear operation

of NORX. Then we adapt the framework previously proposed for ARX designs,

which allows us to automatise the search for differentials and differential

characteristics. We give upper bounds on the differential probability of a

small number of steps of the NORX core permutation, and show how we found the

best characteristics for four rounds, which have probabilities of $2^{-584}$

($32$-bit) and $2^{-836}$ ($64$-bit), respectively. Finally, we discuss some

rotational properties of the core permutation which can be used as a basis for

future studies.

*12:17* [Pub][ePrint]
Improved Differential Cryptanalysis of Round-Reduced Speck, by Itai Dinur
Simon and Speck are families of lightweight block ciphers designed by the U.S. National Security Agency and published in 2013. Each of the families contains 10 variants, supporting a wide range of block and key sizes. Since the publication of Simon and Speck, several research papers analyzed their security using various cryptanalytic techniques. The best previously published attacks on all the 20 round-reduced ciphers are differential attacks, and are described in two papers (presented at FSE 2014) by Abed et al. and Biryukov et al.In this paper, we focus on the software-optimized block cipher family Speck, and describe significantly improved attacks on all of its 10 variants. In particular, we increase the number of rounds which can be attacked by 1, 2, or 3, for 9 out of 10 round-reduced members of the family, while significantly improving the complexity of the previous best attack on the remaining round-reduced member. Our attacks use an untraditional key recovery technique for differential attacks, which resembles techniques typically used in attacks based on self-similarity.

Despite our significantly improved attacks, they do not seem to threaten the security of any member of Speck.

*12:17* [Pub][ePrint]
Statistical weaknesses in 20 RC4-like algorithms and (probably) the simplest algorithm free from these weaknesses - VMPC-R, by Bartosz Zoltak
We find statistical weaknesses in 20 RC4-like algorithms including the original RC4, RC4A, PC-RC4 and others.This is achieved using a simple statistical test.

We found only one algorithm which was able to pass the test - VMPC-R.

This algorithm, being approximately three times more complex then RC4,

is probably the simplest RC4-like cipher capable of producing pseudo-random output.