International Association
for Cryptologic Research

Event date: to
Submission deadline: 31 March 2021

This paper presents the first third-party security analysis of \tinyjambu, which is one of 32 second-round candidates in NIST's lightweight cryptography standardization process. TinyJAMBU adopts an NLFSR based keyed-permutation that computes only a single NAND gate as a non-linear component per round. The designers evaluated the minimum number of active AND gates, however such a counting method neglects the dependency between multiple AND gates. There also exist previous works considering such dependencies with stricter models, however those are known to be too slow. In this paper, we present a new model that provides a good balance of efficiency and accuracy by only taking into account the first-order correlation of AND gates that frequently occurs in TinyJAMBU. With the refined model, we show a 338-round differential with probability $2^{-62.68}$ that leads to a forgery attack breaking 64-bit security. This implies that the security margin of TinyJAMBU with respect to the number of unattacked rounds is approximately 12%. We also show a differential on full 384 rounds with probability $2^{-70.64}$, thus the security margin of full rounds with respect to the data complexity, namely the gap between the claimed security bits and the attack complexity, is less than 8 bits. Our attacks also point out structural weaknesses of the mode that essentially come from the minimal state size to be lightweight.

CHES 2020 will be held from September 14 to 17 as a virtual event.

To register for CHES 2020, please visit the CHES 2020 registration site. Registration for CHES 2020 is free for IACR members; non-IACR members will be asked to pay the IACR membership fee (USD 50 regular, USD 25 for students) during registration.

You can follow any updates on twitter @2020CHES.

We analyze the handshake protocol of the Transport Layer Security (TLS) protocol, version 1.3. We address both the full TLS 1.3 handshake (the one round-trip time mode, with signatures for authentication and (elliptic curve) Diffie–Hellman ephemeral ((EC)DHE) key exchange), and the abbreviated resumption/"PSK" mode which uses a pre-shared key for authentication (with optional (EC)DHE key exchange and zero round-trip time key establishment). Our analysis in the reductionist security framework uses a multi-stage key exchange security model, where each of the many session keys derived in a single TLS 1.3 handshake is tagged with various properties (such as unauthenticated versus unilaterally authenticated versus mutually authenticated, whether it is intended to provide forward security, how it is used in the protocol, and whether the key is protected against replay attacks). We show that these TLS 1.3 handshake protocol modes establish session keys with their desired security properties under standard cryptographic assumptions.

Symmetric password-authenticated key exchange (sPAKE) can be seen as an extension of traditional key exchange where two parties agree on a shared key if and only if they share a common secret (possibly low-entropy) password. We present the first sPAKE protocol to simultaneously achieve the following properties:

- only two exponentiations per party, the same as plain unauthenticated Diffie-Hellman key agreement (and likely optimal);

- optimal round complexity: a single flow (one message from each party that can be sent in parallel) to achieve implicit authentication, or two flows to achieve explicit mutual authentication;

- security in the random oracle model, rather than ideal cipher or generic group model;

- UC security, rather than game-based.

Our protocol is a generalization of the seminal EKE protocol of Bellovin & Merritt (S&P 1992).

We also present a UC-secure 1-out-of-$N$ oblivious transfer (OT) protocol, for random payloads. Its communication complexity is independent of $N$, meaning that $N$ can even be exponential in the security parameter. Such a protocol can also be considered a kind of oblivious PRF (OPRF). Our protocol improves over the leading UC-secure 1-out-of-$N$ OT construction of Masny & Rindal (CCS 2019) for all $N>2$, and has essentially the same cost for $N=2$.

The new technique underlying these results is a primitive we call programmable-once public function (POPF). Intuitively, a POPF is a function whose output can be programmed by one party on exactly one point. All other outputs of the function are outside of any party's control, in a provable sense.

We present a new, simple candidate construction of indistinguishability obfuscation (iO). Our scheme is inspired by lattices and learning-with-errors (LWE) techniques, but we are unable to prove security under a standard assumption. Instead, we formulate a new falsifiable assumption under which the scheme is secure. Furthermore, the scheme plausibly achieves post-quantum security.

Our construction is based on the recent "split FHE" framework of Brakerski, D\"ottling, Garg, and Malavolta (EUROCRYPT '20), and we provide a new instantiation of this framework. As a first step, we construct an iO scheme that is provably secure assuming that LWE holds \emph{and} that it is possible to obliviously generate LWE samples without knowing the corresponding secrets. We define a precise notion of oblivious LWE sampling that suffices for the construction. It is known how to obliviously sample from any distribution (in a very strong sense) using iO, and our result provides a converse, showing that the ability to obliviously sample from the specific LWE distribution (in a much weaker sense) already also implies iO. As a second step, we give a heuristic contraction of oblivious LWE sampling. On a very high level, we do this by homomorphically generating pseudoradnom LWE samples using an encrypted pseudorandom function.

Often in cryptography one needs to make a consistent choice of square root in a finite field. We show that such a choice is equivalent to providing a reasonable sign function. Then we show that for $\mathbb{F}_{p^k}$ (with odd prime $p \neq 1$ and $k\neq 0$) such a sign function exists if and only if $k$ is odd.

We present the Modular Specifications Security (MoSS) framework, where security specifications are defined with respect to a specific model predicate $\cal M$. This allows analysis of even complex schemes and protocols, e.g., PKI schemes, under well-defined adversary, communication and synchronization models, in a modular and flexible way, and allows to analyze such schemes in both simplified and realistic models. The framework facilitates reuse of definitions, and, indeed, several of the model predicates and security specifications we define, seem `generic' and reusable in analysis of other practical protocols.

Blockchain is a multiparty protocol to reach agreement on the order of events, and to record them consistently and immutably without centralized trust. In some cases, however, the blockchain can benefit from some controlled mutability. Examples include removing private information or unlawful content, and correcting protocol vulnerabilities which would otherwise require a hard fork. Two approaches to control the mutability are: moderation, where one or more designated administrators can use their private keys to approve a redaction, and voting, where miners can vote to endorse a suggested redaction. In this paper, we first present several attacks against existing redactable blockchain solutions. Next, we provide a definitional framework for moderated redactable blockchains. Finally, we propose a provable and efficient construct, which applies a single digital signature per redaction, achieving a much simpler and secure result compared to the prior art in the moderated setting.

The Number Theoretic Transform (NTT) is a critical sub-block used in several structured lattice-based schemes, including Kyber and Dilithium, which are finalist candidates in the NIST's standardization process for post-quantum cryptography. The NTT was shown to be susceptible to single trace side-channel attacks by Primas et al. in CHES 2017 and Pessl et al. in Latincrypt 2019 who demonstrated full key recovery from single traces on the ARM Cortex-M4 microcontroller. However, the cost of deploying suitable countermeasures to protect the NTT from these attacks on the same target platform has not yet been studied. In this work, we propose novel shuffling and masking countermeasures to protect the NTT from such single trace attacks. Firstly, we exploit arithmetic properties of twiddle constants used within the NTT computation to propose efficient and generic masking strategies for the NTT with configurable SCA resistance. Secondly, we also propose new variants of the shuffling countermeasure with varying granularity for the NTT. We perform a detailed comparative evaluation of the runtime performances for our proposed countermeasures within open source implementations of Kyber and Dilithium from the pqm4 library on the ARM Cortex-M4 microcontroller. Our proposed countermeasures yield a reasonable overhead in the range of 7%-78% across all procedures of Kyber, while the overheads are much more pronounced for Dilithium, ranging from 12%-197% for the key generation procedure and 32%-490% for the signing procedure.

Although large numbers of hardware and software implementations have been proposed to accelerate lattice-based cryptography, Saber, a module-LWR-based algorithm, which has advanced to second round of the NIST standardization process, has not been adequately supported by the current solutions. Based on these motivations, a high-performance crypto-processor is proposed based on an algorithm-hardware co-design in this paper. First, a hierarchical Karatsuba calculating framework, a hardware-efficient Karatsuba scheduling strategy and an optimized circuit structure are utilized to enable high-throughput polynomial multiplication. Furthermore, a task-level pipeline and truncated multipliers are proposed to enable algorithm-specific fine-grained processing. Enabled by all of the above optimizations, Avalon takes 943, 1156, and 408 clock cycles for key generation, encryption, and decryption, respectively. Enabled by these optimizations, our processor takes 943, 1156 and 408 clock cycles for key generation, encryption, and decryption of Saber768, achieving 5.4x, 5.2x and 4.2x reductions compared with the state-of-the-art FPGA solutions, respectively. The post-layout simulation of our design is implemented with TSMC 40nm CMOS process within 0.35 mm2. The throughput for Saber768 is up to 346k encryption operations per second and the energy efficiency is 0.12uJ/encryption while operating at 400MHz, achieving nearly 52x improvement and 30x improvement, respectively compared with current PQC hardware solutions.

We examine the security of the Australian card payment system by analysing existing cryptographic protocols. In this analysis, we examine TDES and DES-V key derivation and the use of secure cryptographic devices, then contrast this with alternative mechanisms to enable secure card payments. We compare current Australian cryptographic methods with their international counterparts, such as the ANSI methods, and then motivate alternative methods for authenticated encryption in card payment systems.

Komargodski et.al. introduced {\em Evolving Secret Sharing} which allows an imaprtial participant, called \emph{dealer}, to share a secret among unbounded number of participants over any given access structure. In their construction for evolving secret sharing over general access structure, the size of share of the $i^{th}$ participant happens to be exponential $(\mathcal{O}(2^{i-1}))$. They also provided constructions for $(k,\infty)$ threshold secret sharing. We consider the problem of evolving secret sharing with $t$ essential participants, namely, over $t$-$(k,\infty)$ access structure, a generalization of $(k,\infty)$ secret sharing $(t=0)$. We further generalize this access structure to a possible case of unbounded number of essential participants and provide a construction for secret sharing on it. Both the constructions are information theoretically secure and reduce the share size of the construction due to Komargodski et.al. over general access structure, exponentially. Moreover, the essential participants receive ideal (and hence, optimal) shares in the first construction.

In this paper, we revisit the difference enumeration techniques for LowMC and develop new algebraic techniques to achieve efficient key-recovery attacks with negligible memory complexity. \mbox{Benefiting} from our technique to reduce the memory complexity, we could significantly improve the attacks on LowMC when the block size is much larger than the key size and even break LowMC with such a kind of parameter. On the other hand, with our new key-recovery technique, we could significantly improve the time to retrieve the full key if given only a single pair of input and output messages together with the difference trail that they take, which was stated as an interesting question by Rechberger et al. in ToSC 2018. Combining both the techniques, with only 2 chosen plaintexts, we could break 4 rounds of LowMC adopting a full S-Box layer with block size of 129, 192 and 255 bits, respectively, which are the 3 recommended parameters for Picnic3, an alternative \mbox{third-round} candidate in NIST's Post-Quantum Cryptography competition. We have to emphasize that our attacks do not indicate that Picnic3 is broken as the Picnic use-case is very different and an attacker cannot even freely choose 2 plaintexts to encrypt for a LowMC instantiation. However, such parameters are deemed as secure in the latest LowMC. Moreover, much more rounds of seven instances of the backdoor ciphers \mbox{LowMC-M} as proposed by Peyrin and Wang in CRYPTO 2020 can be broken without finding the backdoor by making full use of the allowed $2^{64}$ data. The above mentioned attacks are all achieved with negligible memory.

The Services and Cybersecurity (SCS) group at the University of Twente invites applications for a 4-year PhD position in evidence-based security response.

We are looking for candidates with a solid background in network and system security.

More information and the link to apply:
https://www.utwente.nl/en/organization/careers/!/1097214/full-time-phd-position-in-evidence-based-security-response

Deadline for applications: 30 September 2020, 23:59 CET

Closing date for applications:

Contact: Dr. Andreas Peter (a.peter@utwente.nl)

More information: https://www.utwente.nl/en/organization/careers/!/1097214/full-time-phd-position-in-evidence-based-security-response

Decentralised Randomness Beacon (DRB) is a service that periodically generates publicly verifiable randomness, which plays critical roles in various cryptographic protocols. However, constructing DRB protocols is challenging. Existing DRB protocols suffer from either strong network synchrony assumptions, high communication complexity or attacks. In this paper, we propose RandChain, a new family of permissioned DRB protocols. RandChain is constructed from Sequential Proof-of-Work (SeqPoW) – a Proof-of-Work (PoW) variant that is sequential, i.e., non-parallelisable – and Nakamoto consensus. In RandChain, nodes jointly maintain a blockchain, and each block attaches a random output. Given the last block, each node deterministically derives a SeqPoW puzzle, and keeps solving SeqPoW (aka. mining) until finding a valid solution, of which the value is unpredictable. The first node solving SeqPoW includes a block to the blockchain. The SeqPoW solution’s hash is the random output in this block. RandChain applies Nakamoto consensus so that nodes agree on a unique blockchain. We formalise SeqPoW, propose two constructions, prove their security and evaluate their performance. Our results show that SeqPoW is practical. We then formalise DRBs and analyse RandChain's security. Our analysis shows that RandChain implements a DRB protocol and can produce strongly unpredictable and unbiasible randomness. While as simple and scalable as PoW-based consensus, RandChain achieves better energy efficiency and decentralisation than PoW-based consensus, thanks to the non-parallelisable mining. We also discuss considerations of deploying RandChain in practice, including adding finality, mining non-outsourceability, and difficulty adjustment to RandChain.

This note describes several attacks on the MALICIOUS framework for creating backdoored tweakable block ciphers. It is shown that, although the embedded malicious tweak pair itself is hard to recover, it is feasible to find additional weak tweak pairs that can be used to mount key-recovery attacks. Full-round attacks on most instances of LowMC-M are given. Our attacks are far from optimized and significant future improvements are to be expected.

We focus on low-data attacks, since these are the most relevant for typical use-cases of LowMC. In addition, this implies that our attacks can not be prevented by limiting the amount of data that can be encrypted using the weak tweak pair.

Despite our findings, we believe that the MALICIOUS framework can be used to create backdoored variants of LowMC provided that the parameters are modified.

In this paper we show that deep learning can be used to identify the shape of power traces corresponding to the responses of a protected arbiter PUF implemented in FPGAs. To achieve that, we combine power analysis with bitstream modification. We train a CNN classifier on two 28nm XC7 FPGAs implementing 128-stage arbiter PUFs and then classify the responses of PUFs from two other FPGAs. We demonstrate that it is possible to reduce the number of traces required for a successful attack to a single trace by modifying the bitstream to replicate PUF responses.

At EUROCRYPT 2020, Hosoyamada and Sasaki proposed the first dedicated quantum attack on hash functions --- a quantum version of the rebound attack exploiting differentials whose probabilities are too low to be useful in the classical setting. This work opens up a new perspective toward the security of hash functions against quantum attacks. In particular, it tells us that the search for differentials should not stop at the classical birthday bound. Despite these interesting and promising implications, the concrete attacks described by Hosoyamada and Sasaki make use of large quantum random access memories (qRAMs), a resource whose availability in the foreseeable future is controversial even in the quantum computation community. Without large qRAMs, these attacks incur significant increases in time complexities. In this work, we reduce or even avoid the use of qRAMs by performing a quantum rebound attack based on differentials with non-full-active super S-boxes. Along the way, an MILP-based method is proposed to systematically explore the search space of useful truncated differentials with respect to rebound attacks. As a result, we obtain improved attacks on \aes-\texttt{MMO}, \aes-\texttt{MP}, and the first classical collision attacks on 4- and 5-round \grostl-\texttt{512}. Interestingly, the use of non-full-active super S-box differentials in the analysis of \aes-\texttt{MMO} gives rise to new difficulties in collecting enough starting points. To overcome this issue, we consider attacks involving two message blocks to gain more degrees of freedom, and we successfully compress the qRAM demand of the collision attacks on \texttt{AES}-\texttt{MMO} and \texttt{AES}-\texttt{MP} (EUROCRYPT 2020) from $2^{48}$ to a range from $2^{16}$ to $0$, while still maintaining a comparable time complexity. To the best of our knowledge, these are the first dedicated quantum attacks on hash functions that slightly outperform Chailloux, Naya-Plasencia, and Schrottenloher's generic quantum collision attack (ASIACRYPT 2017) in a model where large qRAMs are not available. This work demonstrates again how a clever combination of classical cryptanalytic technique and quantum computation leads to improved attacks, and shows that the direction pointed out by Hosoyamada and Sasaki deserves further investigation.

We give new proofs that justify the SIGMA and TLS 1.3 key exchange protocols not just in principle, but in practice. By this we mean that, for standardized elliptic curve group sizes, the overall protocol actually achieves the intended security level.

Prior work gave reductions of both protocols' security to the underlying building blocks that were loose (in the number of users and/or sessions), so loose that they gave no guarantees for practical parameters. Adapting techniques by Cohn-Gordon et al. (Crypto 2019), we give reductions for SIGMA and TLS 1.3 to the strong Diffie-Hellman problem which are tight, and prove that this problem is as hard as solving discrete logarithms in the generic group model. Leveraging our tighter and fully-quantitative bounds, we meet the protocols' targeted security levels when instantiated with standardized curves and improve over prior bounds by up to over 80 bits of security across a range of real-world parameters.