International Association
for Cryptologic Research

In recent years, Mixed Integer Linear Programming (MILP) has been widely used in cryptanalysis of symmetric-key primitives. For differential and linear cryptanalysis, MILP can be used to solve the two problems: calculation of the minimum number of differential/linear active S-boxes, and search for the best differential/linear characteristics. There are already numerous papers published in this area which either find differential characteristics with good probabilities or ones with small numbers of active S-boxes. However, the efficiency is not satisfactory enough for many symmetric-key primitives. In this paper, we will greatly improve the efficiency of the search algorithms for both the two problems based on MILP. Solving the problems of the calculation of the minimum number of differential/linear active S-boxes and the search for the best differential/linear characteristics can be equivalent to solving an MILP model whose feasible region is the set of all possible differential/linear characteristics. However, searching the whole feasible region is inefficient and high-probability differential/linear characteristics are likely to appear on the smaller feasible region with a low number of active S-boxes at some round. Inspired by the idea of divide-and-conquer approach, we divide the whole feasible region into smaller ones and separately search them. We apply our method to 5 lightweight block ciphers: PRESENT, GIFT-64, RECTANGLE, LBLOCK and TWINE. For each cipher, we obtain better results than the best-known ones. For the calculation of the minimum number of differential active S-boxes, we can reach 31-round PRESENT, 28-round GIFT-64 and 17-round RECTANGLE respectively. For the search for the best differential characteristics, we can reach 23, 14, 15, 21 and 17 rounds for the five ciphers respectively. Based on the duality between the differential cryptanalysis and the linear cryptanalysis, we leave the case for linear cryptanalysis in our future work.

Robustly reusable Fuzzy Extractor (rrFE) considers reusability and robustness simultaneously. We present two approaches to the generic construction of rrFE. Both of approaches make use of a secure sketch and universal hash functions. The first approach also employs a special pseudo-random function (PRF), namely unique-input key-shift (ui-ks) secure PRF, and the second uses a key-shift secure auxiliary-input authenticated encryption (AIAE). The ui-ks security of PRF (resp. key-shift security of AIAE), together with the homomorphic properties of secure sketch and universal hash function, guarantees the reusability and robustness of rrFE. Meanwhile, we show two instantiations of the two approaches respectively. The first instantiation results in the first rrFE from the LWE assumption, while the second instantiation results in the first rrFE from the DDH assumption over non-pairing groups.

We introduce CHURP (CHUrn-Robust Proactive secret sharing). CHURP enables secure secret-sharing in dynamic settings, where the committee of nodes storing a secret changes over time. Designed for blockchains, CHURP has lower communication complexity than previous schemes: $O(n)$ on-chain and $O(n^2)$ off-chain in the optimistic case of no node failures.

CHURP includes several technical innovations: An efficient new proactivization scheme of independent interest, a technique (using asymmetric bivariate polynomials) for efficiently changing secret-sharing thresholds, and a hedge against setup failures in an efficient polynomial commitment scheme. We also introduce a general new technique for inexpensive off-chain communication across the peer-to-peer networks of permissionless blockchains.

We formally prove the security of CHURP, report on an implementation, and present performance measurements.

Message franking enables cryptographically verifiable reporting of abusive content in end-to-end encrypted messaging. Grubbs, Lu, and Ristenpart recently formalized the needed underlying primitive, what they call compactly committing authenticated encryption (AE), and analyzed the security of a number of approaches. But all known secure schemes are still slow compared to the fastest standard AE schemes. For this reason Facebook Messenger uses AES-GCM for franking of attachments such as images or videos. We show how to break Facebook’s attachment franking scheme: a malicious user can send an objectionable image to a recipient but that recipient cannot report it as abuse. The core problem stems from use of fast but non-committing AE, and so we build the fastest compactly committing AE schemes to date. To do so we introduce a new primitive, called encryptment, which captures the essential properties needed. We prove that, unfortunately, schemes with performance profile similar to AES-GCM won’t work. Instead, we show how to efficiently transform Merkle-Damgärd-style hash functions into secure encryptments, and how to efficiently build compactly committing AE from encryptment. Ultimately our main construction allows franking using just a single computation of SHA-256 or SHA-3. Encryptment proves useful for a variety of other applications, such as remotely keyed AE and concealments, and our results imply the first single-pass schemes in these settings as well.

NTRU lattices are a class of polynomial rings which allow for compact and efficient representations of the lattice basis, thereby offering very good performance characteristics for the asymmetric algorithms that use them. Signature algorithms based on NTRU lattices have fast signature generation and verification, and relatively small signatures, public keys and private keys.

A few lattice-based cryptographic schemes entail, generally during the key generation, solving the NTRU equation: $$ f G - g F = q \mod x^n + 1 $$ Here $f$ and $g$ are fixed, the goal is to compute solutions $F$ and $G$ to the equation, and all the polynomials are in $\mathbb{Z}[x]/(x^n + 1)$. The existing methods for solving this equation are quite cumbersome: their time and space complexities are at least cubic and quadratic in the dimension $n$, and for typical parameters they therefore require several megabytes of RAM and take more than a second on a typical laptop, precluding onboard key generation in embedded systems such as smart cards.

In this work, we present two new algorithms for solving the NTRU equation. Both algorithms make a repeated use of the field norm in tower of fields; it allows them to be faster and more compact than existing algorithms by factors $\tilde O(n)$. For lattice-based schemes considered in practice, this reduces both the computation time and RAM usage by factors at least 100, making key pair generation within range of smart card abilities.

Distributed credit networks, such as Ripple and Stellar, are becoming popular as an alternative means for financial transactions. However, the current designs do not preserve user privacy or are not truly decentralized. In this paper, we explore the creation of a distributed credit network that preserves user and transaction privacy and unlinkability. We propose BlAnC, a novel, fully decentralized blockchain-based credit network where credit transfer between a sender-receiver pair happens on demand. In BlAnC, multiple concurrent transactions can occur seamlessly, and malicious network actors that do not follow the protocols and/or disrupt operations can be identified efficiently. We perform security analysis of our proposed protocols in the universal composability framework to demonstrate its strength, and discuss how our network handles operational dynamics. We also present preliminary experiments and scalability analyses.

Recovering keys efficiently from far beyond exhaustible candidate spaces is a meaningful but very challenging topic in Side-Channel Attacks (SCA). Recent methods often utilize collision optimizations to reduce the key candidate space so that exhaustive search methods can be feasibly applied for key recovery. However, the current collision optimization methods can only utilize information of a small number of collisions, which limits the number of wrong key candidates that can be removed. In addition, their application is restricted to situations where only small thresholds can be applied. As such, the existing methods are not feasible for recovering the full key if sub-keys and collision values are located in much deeper spaces as we will discuss in this paper. To overcome these problems, we propose Full Collision Attack (FCA). Compared to the existing methods, FCA makes use of all possible collisions between any two sub-keys and removes a larger number of wrong key candidates, thus enabling key recovery in much deeper spaces. Moreover, we find that the collision values that fall beyond the threshold usually occurs only for a few sub-keys. Based on this finding, we propose the Rotational Error Tolerant FCA (RET-FCA) to significantly reduce the candidate space of collisions. Our results show that RET-FCA performs favourably when the collision values fall in the intractable space of FCA.

Lightweight cryptography is an important tool for building strong security solutions for pervasive devices with limited resources. Due to the stringent cost constraints inherent in extremely large applications, the efficient implementation of cryptographic hardware and software algorithms is of utmost importance to realize the vision of generalized computing.

In CRYPTO 2016, Beierle, Kranz and Leander have considered lightweight multiplication in ${F}_{2^n}$. Specifically, they have considered the fundamental question of optimizing finite field multiplications with one fixed element and investigated which field representation, that is which choice of basis, allows for an optimal implementation. They have left open a conjecture related to two XOR-count. Using the theory of linear algebra, we prove in the present paper that their conjecture is correct. Consequently, this proved conjecture can be used as a reference for further developing and implementing cryptography algorithms in lightweight devices.

We show that the problem of reconstructing encrypted databases from access pattern leakage is closely related to statistical learning theory. This new viewpoint enables us to develop broader attacks that are supported by streamlined performance analyses.

As an introduction to this viewpoint, we first present a general reduction from reconstruction with known queries to PAC learning. Then, we directly address the problem of $\epsilon$-approximate database reconstruction ($\epsilon$-ADR) from range query leakage, giving attacks whose query cost scales only with the relative error $\epsilon$, and is independent of the size of the database, or the number $N$ of possible values of data items. This already goes significantly beyond the state of the art for such attacks, as represented by Kellaris et al. (ACM CCS 2016) and Lacharit\'{e} et al. (IEEE S&P 2018).

We also study the new problem of $\epsilon$-approximate order reconstruction ($\epsilon$-AOR), where the adversary is tasked with reconstructing the order of records, except for records whose values are approximately equal. We show that as few as ${\mathcal{O}}(\epsilon^{-1} \log \epsilon^{-1})$ uniformly random range queries suffice. Our analysis relies on an application of learning theory to PQ-trees, special data structures tuned to compactly record certain ordering constraints.

We then show that when an auxiliary distribution is available, $\epsilon$-AOR can be enhanced to achieve $\epsilon$-ADR; using real data, we show that devastatingly small numbers of queries are needed to attain very accurate database reconstruction.

Finally, we generalize from ranges to consider what learning theory tells us about the impact of access pattern leakage for other classes of queries, focusing on prefix and suffix queries. We illustrate this with both concrete attacks for prefix queries and with a general lower bound for all query classes.

The main objective of the Internet of Things is to interconnect everything around us to obtain information which was unavailable to us before, thus enabling us to make better decisions. This interconnection of things involves security issues for any Internet of Things key technology. Here we focus on elliptic curve cryptography (ECC) for embedded devices, which offers a high degree of security, compared to other encryption mechanisms. However, ECC also has security issues, such as Side-Channel Attacks (SCA), which are a growing threat in the implementation of cryptographic devices. This paper analyze the state-of-the-art of several proposals of algorithmic countermeasures to prevent passive SCA on ECC defined over prime fields. This work evaluates the trade-offs between security and the performance of side-channel attack countermeasures for scalar multiplication algorithms without pre-computation, i.e. for variable base point. Although a number of results are required to study the state-of-the-art of side-channel attack in elliptic curve cryptosystems, the interest of this work is to present explicit solutions that may be used for the future implementation of security mechanisms suitable for embedded devices applied to Internet of Things. In addition security problems for the countermeasures are also analyzed.

The Learning with Errors problem (LWE) has become a central topic in recent cryptographic research. In this paper, we present a new solving algorithm combining important ideas from previous work on improving the Blum-Kalai-Wasserman (BKW) algorithm and ideas from sieving in lattices. The new algorithm is analyzed and demonstrates an improved asymptotic performance. For the Regev parameters $q=n^2$ and noise level $\sigma = n^{1.5}/(\sqrt{2\pi}\log_{2}^{2}n)$, the asymptotic complexity is $2^{0.893n}$ in the standard setting, improving on the previously best known complexity of roughly $2^{0.930n}$. The newly proposed algorithm also provides asymptotic improvements when a quantum computer is assumed or when the number of samples is limited.

Persistent fault analysis (PFA) was proposed at CHES 2018 as a novel fault analysis technique. It was shown to completely defeat standard redundancy based countermeasure against fault analysis. In this work, we investigate the security of masking schemes against PFA. We show that with only one fault injection, masking countermeasures can be broken at any masking order. The study is performed on publicly available implementations of masking.

The design of modern stream ciphers is strongly influenced by the fact that Time-Memory-Data tradeoff attacks (TMD-TO attacks) reduce their effective key length to $\mathit{SL}/2$, where $\mathit{SL}$ denotes the inner state length. The classical solution, employed, e.g., by eSTREAM portfolio members Trivium and Grain v1, is to design the cipher in accordance with the Large-State-Small-Key construction, which implies that $\mathit{SL}$ is at least twice as large as the session key length $\mathit{KL}$.

In the last years, a new line of research looking for alternative stream cipher constructions guaranteeing a higher TMD-TO resistance with smaller inner state lengths has emerged. So far, this has led to three generic constructions: the LIZARD construction, having a provable TMD-TO resistance of $2\cdot \mathit{SL}/3$; the Continuous-Key-Use construction, underlying the stream cipher proposals Sprout, Plantlet, and Fruit; and the Continuous-IV-Use construction, very recently proposed by Hamann, Krause, and Meier. Meanwhile, it could be shown that the Continuous-Key-Use construction is vulnerable against certain nontrivial distinguishing attacks.

In this paper, we present a formal framework for proving security lower bounds on the resistance of generic stream cipher constructions against TMD-TO attacks and analyze two of the constructions mentioned above. First, we derive a tight security lower bound of approximately $\min\{\mathit{KL},\mathit{SL}/2\}$ on the resistance of the Large-State-Small-Key construction. This shows that the feature $\mathit{KL}\le \mathit{SL}/2$ does not open the door for new nontrivial TMD-TO attacks against Trivium and Grain v1 which are more dangerous than the known ones. Second, we prove a maximal security bound on the TMD-TO resistance of the Continuous-IV-Use construction, which shows that designing concrete instantiations of ultra-lightweight Continuous-IV-Use stream ciphers is a hopeful direction of future research.

We introduce the notion of two-factor signatures (2FS), a generalization of a two-out-of-two threshold signature scheme in which one of the parties is a hardware token which can store a high-entropy secret, and the other party is a human who knows a low-entropy password. The security (unforgeability) property of 2FS requires that an external adversary corrupting either party (the token or the computer the human is using) cannot forge a signature. This primitive is useful in contexts like hardware cryptocurrency wallets in which a signature conveys the authorization of a transaction. By the above security property, a hardware wallet implementing a two-factor signature scheme is secure against attacks mounted by a malicious hardware vendor; in contrast, all currently used wallet systems break under such an attack (and as such are not secure under our definition). We construct efficient provably-secure 2FS schemes which produce either Schnorr signature (assuming the DLOG assumption), or EC-DSA signatures (assuming security of EC-DSA and the CDH assumption) in the Random Oracle Model, and evaluate the performance of implementations of them. Our EC-DSA based 2FS scheme can directly replace currently used hardware wallets for Bitcoin and other major cryptocurrencies to enable security against malicious hardware vendors.

While financially advantageous, outsourcing key steps such as testing to potentially untrusted Outsourced Semiconductor Assembly and Test (OSAT) companies may pose a risk of compromising on-chip assets. Obfuscation of scan chains is a technique that hides the actual scan data from the untrusted testers; logic inserted between the scan cells, driven by a secret key, hide the transformation functions between the scan- in stimulus (scan-out response) and the delivered scan pattern (captured response). In this paper, we propose ScanSAT: an attack that transforms a scan obfuscated circuit to its logic- locked version and applies a variant of the Boolean satisfiability (SAT) based attack, thereby extracting the secret key. Our empirical results demonstrate that ScanSAT can easily break naive scan obfuscation techniques using only three or fewer attack iterations even for large key sizes and in the presence of scan compression.

Relay attacks are nowadays well known and most designers of secure authentication protocols are aware of them. At present, the main methods to prevent these attacks are based on the so-called distance bounding technique which consists in measuring the round-trip time of the exchanged authentication messages between the prover and the verifier to estimate an upper bound on the distance between these entities. Based on this bound, the verifier checks if the prover is sufficiently close by to rule out an unauthorized entity. Recently, a new work has proposed an authentication protocol that surprisingly uses the side-channel leakage to prevent relay attacks. In this paper, we exhibit some practical and security issues of this protocol and provide a new one that fixes all of them. Then, we argue the resistance of our proposal against both side-channel and relay attacks under some realistic assumptions. Our experimental results show the efficiency of our protocol in terms of false acceptance and false rejection rates.

Logic locking has been proposed as a strong protection of intellectual property (IP) against security threats in the IC supply chain especially when the fabrication facility is untrusted. Various techniques have proposed circuit configurations which do not allow the untrusted fab to decipher the true functionality and/or produce usable versions of the chip without having access to the locking key. These techniques rely on using additional locking circuitry which injects incorrect behavior into the digital functionality when the key is incorrect. However, much of this conventional research focuses on locking individual modules (such as adders, ALUs etc.). While locking these modules is useful, the true test for any locking scheme should consider their impact on the application running on a processor with such modules. A locked module within a processor may or may not have a substantial impact at the application level thereby allowing the attacker (untrusted foundry or unauthorized user) to still get useful work out of the system despite not having access to the key details. In this work, we show that even when state of the art locking schemes are used to lock the modules within a processor, a large class of workloads derived from machine learning (ML) applications (which are increasingly becoming the most relevant ones) continue to function correctly. This has huge implications to the effectiveness of the current locking techniques. The main reason for this behavior is the inherent error resiliency of such applications. To counter this threat, we propose a novel secure and effective logic locking scheme, called Strong Anti-SAT (SAS), to lock the entire processor and make sure that the ML applications undergo significant accuracy loss when any wrong key is applied. We provide two types of SAS, namely SAS-A and SAS-B. Experiments show that, for both types of SAS, 1) the application-level accuracy loss is significant (for ML applications) given any wrong key, 2) the attacker needs extremely long time to find a correct key, and 3) the hardware overhead is very small. Lastly, even though our techniques target machine learning type application workloads, the impact on conventional workloads will also be similar. Due to the inherent error resilience of ML, locking ML workloads is a harder problem to tackle.

Group signature scheme provides group members a way to sign messages without revealing their identities. Anonymity and traceability are two essential properties in a group signature system. However, these two security properties hold based on the assumption that all the signing keys are perfectly secret and leakage-free. On the another hand, on account of the physical imperfection of cryptosystems in practice, malicious attackers can learn fraction of secret state (including secret keys and intermediate randomness) of the cryptosystem via side-channel attacks, and thus breaking the security of whole system.

To address this issue, Ono et al. introduced a new security model of group signature, which captures randomness exposure attacks. They proved that their proposed construction satisfies the security require-ments of group signature scheme. Nevertheless, their scheme is only provably secure against randomness exposure and supposes the secret keys remains leakage-free. In this work, we focus on the security model of leakage-resilient group signature based on bounded leakage setting and propose three new black-box constructions of leakage-resilient group signature secure under the proposed security models.

Open Position for Research Fellow in National University of Singapore

“NUS-Singtel Cyber Security R&D Lab” (http://nus-singtel.nus.edu.sg/) is a 5 years joint project with about SGD 43 mil (approximately USD 31 mil) of funds contributed by Singapore Telecommunications Limited (SingTel), National University of Singapore (NUS), and National Research Foundation (NRF) of Singapore. The R&D Lab will conduct research in four broad areas of cyber security having strategic relevance to Singtel’s business: (1) Predictive Security Analytics; (2) Network, Data and Cloud Security; (3) Internet-of-Things and Industrial Control Systems; (4) Future-Ready Cyber Security Systems.

NUS-SingTel Lab currently has one research fellow position with competitive pay. It is available to (fresh) PhD graduates in computer science/engineering from Singapore or overseas.

The Research Fellow will be responsible for working closely with the Principal Investigator and lab members on a new 3-year research project which just started in June 2018. He/she should possess experience or interest in at least some of the following research areas:

• Key management, Authentication, Authorization and Access control

• Trusted computing (e.g. TPM, Intel SGX)

• Post-quantum cryptography

Job requirements:

• A PhD degree in a relevant area (Computer Science/Engineer, mathematics, etc);

• Good publication record in cyber security and crypto area

• Publication in Rank 1 Cyber Security or Crypto Conference, or AsiaCrypt, ESORICS, ACSAC, TCC, Euro S&P, etc;

• Good communication skills, self-motivated and good team players;

• Some experience in programming is a plus;

• Willing to perform practical research which may eventually lead to products

To apply for the above position, please send a copy of your recent CV to \"comxj at nus.edu.sg\" with an email subject “Application for RF”.

Closing date for applications: 1 June 2019

Contact: Dr Xu,

comxj at nus.edu.sg

More information: https://www.nus-singtel.nus.edu.sg/

Singapore University of Technology and Design (SUTD) is a young university which was established in collaboration with MIT. iTrust is a Cyber Security Research Center which has the world\'s best facilities in cyber-physical systems (CPS) including testbeds for Secure Water Treatment (SWaT), Water Distribution (WADI), Electric Power and Intelligent Control (EPIC), and IoT. (See more info at https://itrust.sutd.edu.sg/research/testbeds/.)

I am looking for PhD interns with interest in cyber-physical system security (IoT, power grid, water, transportation, and autonomous vehicle etc.). The attachment will be at least 3 months. Allowance will be provided for local expenses.

Interested candidates please send your CV with a research statement to Prof. Jianying Zhou. Only short-listed candidates will be contacted for interview.

Closing date for applications: 31 March 2019

Contact: Prof. Jianying Zhou

More information: http://jianying.space/