Home Research Projects Thesis Contact

Passwords are widely used to protect secret data or to gain access to specific resources. Full disk encryption, authentication to web services, authentication to mobile devices, are examples of real applications. For sake of security, passwords should be strong enough to prevent well-know attacks, in particular dictionary and brute force attacks. Unfortunately, user-chosen passwords are generally short and lacks enough entropy. For these reasons, passwords cannot be directly used as a key to implement secure cryptographic systems. A possible solution to these issues is to adopt a password-based key derivation function (KDF), that is a function which takes a source of initial keying material and derives from it one or more pseudo-random keys. By applying a KDF to a user password, we (1) allow to increase the size of a cryptographic key, (2) allow legitimate users to spend a moderate amount of time on key derivation, and (3) slow down a brute force attack as much as possible. In this research project we analyze algorithms and cryptographic primitives used to generate keys with the aim to find weaknesses and suggest possible solutions [1,2]. Particular attention will be paid to security and performance matters.

[1] A.Visconti, S.Bossi, H.Ragab, A.Calò. On the Weaknesses of PBKDF2. In Proceedings of the 14th International Conference on Cryptology and Network Security (CANS 2015), LNCS 9476, pp.119--126 pdf.

[2] S.Bossi, A.Visconti. What Users Should Know About Full Disk Encryption Based on LUKS. In Proceedings of the 14th International Conference on Cryptology and Network Security (CANS 2015), LNCS 9476, pp.225--237 pdf.

Keccak [1] is a family of sponge functions, winner of the SHA-3 contest [2] announced by the NIST. The iterated permutation underlying Keccak, indicated by Keccak-f [b], consists of a sequence of rounds operating on GF(2)b, where b (called the width of the permutation) belongs to {25,50,100,200,400,800,1600}.

Differential cryptanalysis (DC) and Linear cryptanalysis (LC) attempt to find and exploit predictable propagation patterns to break iterative cryptographic primitives. For ciphers this typically means key retrieval, while for hash functions means the possibility to generate preimage or second preimage attacks. DC makes use of differential trails, that consist of a sequence of differences through the rounds of the primitive. Given such a trail, one can estimate its differential probability (DP), namely, the fraction of all possible input pairs with the initial trail difference that also exhibit all intermediate and final difference when going through the rounds. LC makes use of linear trails that describe the propagation of masks through the rounds of the primitive. Given such a trail, one can estimate its correlation contribution (C), namely, the correlation between input and output masks, considering the sequence of intermediate masks. A natural way to characterize the power of trails in unkeyed primitives is by their weight w. For differential trails, the weight of a trail is the negative of the binary logarithm of its DP and it can be decomposed in the sum of the weight of its round differentials. For linear trails, the weight is defined as minus the binary logarithm of the square of its C and it can be decomposed in the sum of the weight of its round correlations. In other words, a good approximation for the DP of a differential trail is given by DP=2 -w and the magnitude of the correlation contribution of a linear trail is given by C=2-w. It follows that exploiting such trails, for breaking the cryptographic primitive, becomes harder as the weight increases.

In this project, the research group focus on DC and LC with the aim to show that differential and linear trails cannot be used to construct structural distinguisher in the cryptographic primitive Keccak. Interesting results can be established by finding a lower bound on the weight of any trail over a specified number of rounds. Some results have been published in [3], [4] and [5]. Notice that finding a trail over n rounds with a given weight does not provide a bound. In fact, it is necessary to completely scan the space of n-round trails (up to a given weight) to find the trail with minimum weight. The KeccakTools package [5] implements techniques to generate all n-round differential and linear trails in Keccak-f [b] up to a given weight T. It has been used in [4] to completely scan the space of 3-round (of twenty-four) differential trails up to a weight T=36, for Keccak-f [1600]. Unfortunately, as the three parameters n, T and b increase, timing and memory requirements increase. Our goal is to parallelize, optimize and extend the KeccakTools package, in order to completely scan the space of both linear and differential trails for a bigger number n of rounds and for higher values of the limit weight T, for all the widths b of Keccak-f. If successful, this research would show that differential and linear cryptanalysis cannot be used to attack the winner of the NIST hash function competition: Keccak.

G.M. Bertoni (ST), J. Daemen (ST), S. Mella (UNIMI), G. Van Assche (ST), A. Visconti (UNIMI)

[1] G. Bertoni, J. Daemen, M. Peeters , G. Van Assche. The Keccak SHA-3 submission. http://keccak.noekeon.org/Keccak-submission-3.pdf.

[2] NIST. Announcing request for candidate algorithm nominations for a new cryptographic hash algorithm (SHA-3) family. Federal Register Notices 72 (2007), no. 212, 6221262220. http://csrc.nist.gov/groups/ST/hash/index.html.

[3] G. Bertoni, J. Daemen, M. Peeters , G. Van Assche. The Keccak reference. http://keccak.noekeon.org/Keccak-reference-3.0.pdf.

[4] J. Daemen, G. Van Assche. Differential propagation analysis of Keccak. Fast Software Encryption (FSE'12). http://dx.doi.org/10.1007/978-3-642-34047-5_24.

[5] A. Duc, J. Guo, T. Peyrin, and L. Wei, Unaligned rebound attack: Application to Keccak. Fast Software Encryption (FSE'12).

[6] KeccakTools. https://github.com/gvanas/KeccakTools.

Cryptography and Coding Laboratory @ Department of Computer Science

Università degli Studi di Milano

2015