Research Projects

(2017-present) Grant for an italian blockchain project (ITA only) -- Obiettivo immagine: Estetica della fotografia e cultura del territorio

Il progetto è finalizzato a promuovere un forte impatto culturale sul territorio e sul tessuto sociale, a partire dalla cultura dell'immagine e della fotografia. Gli obiettivi del progetto saranno (a) la sperimentazione di un modello inedito di certificazione estetica (Dipartimento di Beni Culturali e Ambientali); (b) la tutela dei diritti d'autore di giovani artisti attraverso tecniche crittografiche largamente implementate in sistemi basati su blockchain (Dipartimento di Informatica); (c) la valorizzazione di nuovi talenti artistici (Accademia di Brera). Particolare attenzione verrà anche dedicata all'attività didattica e alla formazione di una nuova figura professionale. L'obiettivo sarà quello di formare certificatori che sappiano valorizzare nuovi percorsi artistici/tecnici, superare i limiti imposti dal mercato dell'arte tradizionale e agire sul territorio nel mercato del lavoro. Infine, la divulgazione al pubblico dei risultati ottenuti avverrà attraverso la realizzazione di una serie di mostre sul territorio in luoghi non convenzionali.


(2017-2018) Optimization of Groebner Basis computations for ECDLP

Several cryptographic schemes base their security upon the hardness of the discrete logarithm problem for elliptic curves (ECDLP). In recent years many papers have appeared investigating the classical discrete logarithm problem for elliptic curves, exploiting the multivariate polynomial approach with the use of the celebrated summation polynomials, introduced by Semaev in 2004. However, with a notable exception by Petit et al. in 2016, all numerous specialized papers have investigated only the composite-field case, leaving apart the laborious prime-field case. Recently, a variation of Semaev's original approach for the prime-field case was proposed. Such a variation outperforms both the original Semaev's method and Petit's specialized algorithm. It reaches the improvement by reducing the necessary Groebner basis computations to only one basis calculation. In this project, the research group focuses on the analysis of systems arising from the application of the algorithm in to instances of the ECDLP. The best known algorithms (in terms of efficiency) for computing Groebner Basis are F4 and F5. However, they are "general purpose", i.e. usable for every system of polynomial equations. Consequently, as the cardinality of the base field of the considered elliptic curve grows, it becomes infeasible to solve the corresponding system with F4 and F5. Nevertheless, systems of our interest are very specific, since they are composed by a summation polynomial Sm and univariate polynomials of low degrees. Our aim is to identify recurring patterns, applying F4 to systems arising from elliptic curves field defined over a base field with more than 2^25 elements. Recurrings will lead to an F4's variation, particularly suitable, in terms of efficiency, for systems of cryptographic interest. Improvements on F4 needs to be tested on elliptic curves having domain parameters of cryptographic interest.


(2015-2018) Analysis of Password-Based Key Derivation Functions

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. Particular attention will be paid to security [3,4] and performance matters [1,2,5].


[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.

[3] L.Casati, A.Visconti, Exploiting a Bad User Practice to Retrieve Data Leakage on Android Password Managers In Advances in Intelligent Systems and Computing, 11th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS 2017), LNCS 612.

[4] L.Casati, A.Visconti, The Dangers of Rooting: Data Leakage Detection in Android Application Mobile Information Systems, Article ID 6020461, ISSN 1574-017X, Feb 2018. pdf.

[5] A.Visconti, F.Gorla Exploiting an HMAC-SHA-1 optimization to speed up PBKDF2 . pdf.

(2014) Differential and Linear Cryptanalysis in Evaluating Keccak

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 focuses 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.


[1] G. Bertoni, J. Daemen, M. Peeters , G. Van Assche. The Keccak SHA-3 submission.

[2] NIST. Announcing request for candidate algorithm nominations for a new cryptographic hash algorithm (SHA-3) family. Federal Register Notices 72 (2007), no. 212, 62212–62220.

[3] G. Bertoni, J. Daemen, M. Peeters , G. Van Assche. The Keccak reference.

[4] J. Daemen, G. Van Assche. Differential propagation analysis of Keccak. Fast Software Encryption (FSE'12).

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

[6] KeccakTools.