International Association
for Cryptologic Research

Securing components for the IoT market, as well as critical cyberphysical infrastructures, requires analyzing their vulnerabilities and defining hardware and software countermeasures at the fair cost. The increasing complexity of the processors and the applications they run means that the software fault models (such as instruction skips, or instruction replacement) usually used to analyze the vulnerability of their code are no longer sufficient to express the diversity of faulty behaviors in modern architectures [1]. Indeed, architecture designers have progressively added many complex hardware blocks (such as pipeline, cache memory, branch prediction, or speculative execution) to processors in order to optimize program execution. At the same time, fault injection techniques are constantly progressing (e.g., localized ElectroMagnetic or laser attacks, glitch injection attacks) allowing today higher-order injections (both multi-temporal and multi-spatial). Faced with these attacks, designers must implement countermeasures to detect or mask the effects of injected faults. These countermeasures can be implemented at the hardware level (e.g., duplication of elements, error correcting codes, isolation mechanisms) or at the software level (e.g., duplication of instructions or algorithms, insertion of security tests, signature verification). The design and validation of these countermeasures requires a realistic representation of the effects of faulty attacks (fault model) at the hardware and/or software level. The difficulties encountered are then: (1) the relevance of the fault models: do these fault models correctly represent the effects that an attacker can generate on a target processor? (2) the adequacy of countermeasures: do the countermeasures effectively protect the system, are they oversized and therefore too costly? (3) the link between software and hardware countermeasures: how to combine software and hardware countermeasures efficiently and at the fair cost, how to link the different levels for fault modeling? The CLAM project and the thesis that we propose aim to answer these questions by associating 3 French laboratories with complementary specialties.

Closing date for applications:

Contact: vincent.beroulle(at)lcis.grenoble-inp.fr; paolo.maistri(at)univ-grenoble-alpes.fr

More information: https://lcis.grenoble-inp.fr/medias/fichier/clam-thesis-subject-lcis-valence-en-_1592239520450-pdf?ID_FICHE=559219&INLIN

The Department of Information Technology at Uppsala University invites applications for an Associate Professor in Computer Science with specialization in Cybersecurity The department hosts many successful research efforts on different aspects of cybersecurity, which have attracted a significant amount of external funding. We are now in the process to establish cybersecurity as a strong and visible area in research and teaching. The holder of the position is expected to develop a teaching and research profile in cybersecurity, as well as to take leadership responsibilities in cybersecurity activities within the department. Application Deadline: June 22.

Closing date for applications:

Contact: Christian Rohner (christian.rohner@it.uu.se)

More information: https://uu.se/en/about-uu/join-us/details/?positionId=325568

The new-age processor is going to require hardware-oriented solutions as a primary design criterion for the security against threats. Alternative computational architectures proposed in recent years drive this idea by the inclusion of multi-value logic operations. The realization of multi-value logic gates and testing the advantages of polymorphic inputs and outputs of a circuit, however, remains elusive due to the existing technology gap. In this project, we put forward a new logic-locking framework that will allow us to incorporate multi-value and multi-layer logic with existing CMOS-based logic-locking architectures. Enabling future-generation processors with BioNanoLock is the prime target of the project with small (10-100 logic gates) to medium-sized (100-10000 logic gates) circuits as an intermediate goal. We also envision developing heterogeneous integrated systems for secure information processing in the long-term. In BioNanoLock, an encoded DNA sequence acts as a secret ‘biological activation-key’. This key is molecularly recognized as a unique and secret pattern of key-gates (called biological key-gates) or activates them. This, in turn, enables the CMOS-based key-gates in the logic-locked circuit with the appropriate key value. Different voltage-levels in the multi-valued logic define the “on” or “off” state of the key-gates, thereby adding another level of ambiguity for an attacker and making it harder for the attacker to unlock the circuit. Moving away from the classical CMOS-based techniques for logic locking, the BioNanoLock project enables the researchers to delve into novel logic locking techniques. The project also provides opportunities to map the new logic locking paradigms and attack methodologies to a different class of problems in the complexity theory. As novel simulation methodologies are unexplored in the interdisciplinary domain, the project provides ample opportunities for research and innovation.

Closing date for applications:

Contact: Dr. Farhad Merchant (farhad.merchant@ice.rwth-aachen.de)

More information: https://www.ice.rwth-aachen.de/institute/jobs/job-offer-research-assistant-phd-student-for-bionanolock-project-1/

The candidates for the NIST Post-Quantum Cryptography standardization have undergone extensive studies on efficiency and theoretical security, but research on their side-channel security is largely lacking. This remains a considerable obstacle for their real-world deployment, where side-channel security can be a critical requirement. This work describes a side-channel resistant instance of Saber, one of the lattice-based candidates, using masking as a countermeasure. Saber proves to be very efficient to mask due to two specific design choices: power-of-two moduli, and limited noise sampling of learning with rounding. A major challenge in masking lattice-based cryptosystems is the integration of bit-wise operations with arithmetic masking, requiring algorithms to securely convert between masked representations. The described design includes a novel primitive for masked logical shifting on arithmetic shares, as well as adapts an existing masked binomial sampler for Saber. An implementation is provided for an ARM Cortex-M4 microcontroller, and its side-channel resistance is experimentally demonstrated. The masked implementation features a 2.5x overhead factor, significantly lower than the 5.7x previously reported for a masked variant of NewHope. Masked key decapsulation requires less than 3,000,000 cycles on the Cortex-M4 and consumes less than 12kB of dynamic memory, making it suitable for deployment in embedded platforms.

Database management systems (DBMS) are one of cloud services with great interests in industry and business. In such services, since there is no trust in the cloud servers, the databases are encrypted prior to outsourcing. One of the most challenging issues in designing these services is supporting SQL join queries on the encrypted database. The multi-adjustable join scheme (M-Adjoin) [Khazaei-Rafiee 2019], an extension of Adjoin [Popa-Zeldovich 2012 and Mironov-Segev-Shahaf 2017], is a symmetric-key primitive that supports the join queries for a list of column labels on an encrypted database. In previous works, the following security notions were introduced for Adjoin and M-Adjoin schemes: 3Partition, M3Partition and M3P k , for every integer k . Additionally, simulation-based and indistinguishability-based security notions have been defined by Mironov et al. for Adjoin scheme. In this paper, we extend their results to M-Adjoin and study the relations between all security notions for M-Adjoin. Some non-trivial relations are proved which resolve some open problems raised by [Mironov-Segev-Shahaf 2017].

PMAC is a rate-1, parallelizable, block-cipher-based message authentication code (MAC), proposed by Black and Rogaway (EUROCRYPT 2002). Improving the security bound is a main research topic for PMAC. In particular, showing a tight bound is the primary goal of the research, since Luykx et al.'s paper (EUROCRYPT 2016). Regarding the pseudo-random-function (PRF) security of PMAC, a collision of the hash function, or the difference between a random permutation and a random function offers the lower bound $\Omega(q^2/2^n)$ for $q$ queries and the block cipher size $n$. Regarding the MAC security (unforgeability), a hash collision for MAC queries, or guessing a tag offers the lower bound $\Omega(q_m^2/2^n + q_v/2^n)$ for $q_m$ MAC queries and $q_v$ verification queries (forgery attempts). The tight upper bound of the PRF-security $O(q^2/2^n)$ of PMAC was given by Ga\v{z} et el. (ToSC 2017, Issue 1), but their proof requires a 4-wise independent masking scheme that uses 4 $n$-bit random values. Open problems from their work are: (1) find a masking scheme with three or less random values with which PMAC has the tight upper bound for PRF-security; (2) find a masking scheme with which PMAC has the tight upper bound for MAC-security.

In this paper, we consider PMAC with three powering-up masks that uses three random values for the masking scheme. We show that the PMAC has the tight upper bound $O(q^2/2^n)$ for PRF-security, which answers the open problem (1), and the tight upper bound $O(q_m^2/2^n + q_v/2^n)$ for MAC-security, which answers the open problem (2). Note that these results deal with two-key PMAC, thus showing tight upper bounds of PMACs with single-key and/or with two (or one) powering-up masks are open problems.

Time-locked puzzles---problems whose solution requires some amount of (inherently) sequential effort---have seen a recent increase in popularity (e.g., in the context of verifiable delay functions). Most constructions rely on the conjecture that, given a random~$x$, computing $x^{2^T} \bmod N$ requires at least $T$ (sequential) steps. We study the security of time-locked primitives from two perspectives:

We give the first hardness result about the sequential squaring conjecture. Namely, we show that even in (a quantitative version of) the algebraic group model, any speed up of sequential squaring is as hard as factoring~$N$.

We then focus on \emph{timed commitments}, one of the most important primitives that can be obtained from time-locked puzzles. We extend existing security definitions to settings that may arise when using timed commitments in higher-level protocols. We then give the first construction of \emph{non-malleable} timed commitments. As a building block of independent interest, we also define (and give constructions for) a new primitive called \emph{time-released public-key encryption}.

We present a new protocol for two-party private set intersection (PSI) with semi-honest security in the plain model and one-sided malicious security in the random oracle model. Our protocol achieves a better balance between computation and communication than existing PSI protocols. Specifically, our protocol is the fastest in networks with moderate bandwidth (e.g., $30 - 100$ Mbps). Considering the monetary cost (proposed by Pinkas et al. in CRYPTO 2019) to run the protocol on a cloud computing service, our protocol also compares favorably.

Underlying our PSI protocol is a new lightweight multi-point oblivious pesudorandom function (OPRF) protocol based on oblivious transfer (OT) extension. We believe this new protocol may be of independent interest.

We present our discovery of a group of side-channel vulnerabilities in implementations of the ECDSA signature algorithm in a widely used Atmel AT90SC FIPS 140-2 certified smartcard chip and five cryptographic libraries (libgcrypt, wolfSSL, MatrixSSL, SunEC/OpenJDK/Oracle JDK, Crypto++). Vulnerable implementations leak the bit-length of the scalar used in scalar multiplication via timing. Using leaked bit-length, we mount a lattice attack on a 256-bit curve, after observing enough signing operations. We propose two new methods to recover the full private key requiring just 500 signatures for simulated leakage data, 1200 for real cryptographic library data, and 2100 for smartcard data.

The number of signatures needed for a successful attack depends on the chosen method and its parameters as well as on the noise profile, influenced by the type of leakage and used computation platform. We use the set of vulnerabilities reported in this paper, together with the recently published TPM-FAIL vulnerability as a basis for real-world benchmark datasets to systematically compare our newly proposed methods and all previously published applicable lattice-based key recovery methods. The resulting exhaustive comparison highlights the methods' sensitivity to its proper parametrization and demonstrates that our methods are more efficient in most cases. For the TPM-FAIL dataset, we decreased the number of required signatures from approximately 40 000 to mere 900.

An increasing number of lightweight cryptographic primitives have been published recently. Some of these proposals are ARX primitives, which have shown a great performance in software. Rotational-XOR cryptanalysis is a statistical technique to attack ARX primitives. In this paper, a computer tool to speed up and make easier the security evaluation of ARX block ciphers against rotational-XOR cryptanalysis is shown. Our tool takes a Python implementation of an ARX block cipher and automatically finds an optimal rotational-XOR characteristic. Compared to most of the automated tools, which only support a small set of primitives, our tool supports any ARX block cipher and it is executed with a simple shell command.

We consider the theoretically-sound selection of cryptographic parameters, such as the size of algebraic groups or RSA keys, for TLS 1.3 in practice. While prior works gave security proofs for TLS 1.3, their security loss is quadratic in the total number of sessions across all users, which due to the pervasive use of TLS is huge. Therefore, in order to deploy TLS 1.3 in a theoretically-sound way, it would be necessary to compensate this loss with unreasonably large parameters that would be infeasible for practical use at large scale. Hence, while these previous works show that in principle the design of TLS 1.3 is secure in an asymptotic sense, they do not yet provide any useful concrete security guarantees for real-world parameters used in practice. In this work, we provide a new security proof for the cryptographic core of TLS 1.3, which reduces the security of TLS 1.3 tightly (that is, with constant security loss) to the (multi-user) security of its building blocks. For some building blocks, such as the symmetric record layer encryption scheme, we can then rely on prior work to establish tight security. For others, such as the RSA-PSS digital signature scheme currently used in TLS 1.3, we obtain at least a linear loss in the number of users, independent of the number of sessions, which is much easier to compensate with reasonable parameters. Our work also shows that by replacing the RSA-PSS scheme with a tightly-secure scheme (e. g., in a future TLS version), one can obtain the first fully tightly-secure TLS protocol. Our results enable a theoretically-sound selection of parameters for TLS 1.3, even in large-scale settings with many users and sessions per user.

Secret sharing enables a dealer to split a secret into a set of shares, in such a way that certain authorized subsets of share holders can reconstruct the secret, whereas all unauthorized subsets cannot. Non-malleable secret sharing (Goyal and Kumar, STOC 2018) additionally requires that, even if the shares have been tampered with, the reconstructed secret is either the original or a completely unrelated one.

In this work, we construct non-malleable secret sharing tolerating p-time joint-tampering attacks in the plain model (in the computational setting), where the latter means that, for any p>0 fixed {\em a priori}, the attacker can tamper with the same target secret sharing up to p times. In particular, assuming one-to-one one-way functions, we obtain:

- A secret sharing scheme for threshold access structures which tolerates joint p-time tampering with subsets of the shares of maximal size ({\em i.e.}, matching the privacy threshold of the scheme). This holds in a model where the attacker commits to a partition of the shares into non-overlapping subsets, and keeps tampering jointly with the shares within such a partition (so-called {\em selective partitioning}).

- A secret sharing scheme for general access structures which tolerates joint p-time tampering with subsets of the shares of size $O(\sqrt{\log n})$, where n is the number of parties. This holds in a stronger model where the attacker is allowed to adaptively change the partition within each tampering query (so-called {\em adaptive partitioning}).

At the heart of our result for selective partitioning lies a new technique showing that every one-time {\em statistically} non-malleable secret sharing against joint tampering is in fact {\em leakage-resilient} non-malleable ({\em i.e.},\ the attacker can leak jointly from the shares prior to tampering). We believe this may be of independent interest, and in fact we show it implies lower bounds on the share size and randomness complexity of statistically non-malleable secret sharing against {\em independent} tampering.

Accumulators provide compact representations of large sets and enjoy compact membership witnesses. Besides constant-size witnesses, public-key accumulators provide efficient updates of both the accumulator itself and the witness; however, they come with two drawbacks: they require a trusted setup and -- without knowledge of the secret trapdoors -- their performance is not practical for real-world applications with large sets. Recent improvements in the area of secure multi-party computation allow us to replace the trusted setup with a distributed generation of the public parameters.

In this paper, we introduce multi-party public-key accumulators dubbed dynamic linear secret-shared accumulators. We present versions of dynamic public-key accumulators in bilinear groups giving access to more efficient witness generation and update algorithms that utilize the shares of the secret trapdoors sampled by the parties generating the public parameters.Specifically, for the $t$-SDH-based accumulators, we provide a maliciously-secure variant sped up by a secure multi-party computation (MPC) protocol (IMACC'19) built on top of SPDZ. For this scheme, a performant proof-of-concept implementation is provided, which substantiates the practicability of public-key accumulators in this setting. With our implementation in two MPC frameworks, MP-SPDZ and FRESCO, we obtain more efficient accumulators for both medium-sized ($2^{10}$) and large ($2^{14}$ and above) accumulated sets.

Finally, we explore applications of dynamic linear secret-shared accumulators to revocations schemes of group signatures and credentials system. In particular, we consider it as part of Sovrin's system for anonymous credentials where credentials are issued by the a foundation of trusted nodes. Hence, our accumulators naturally fit this setting.

Pedersen commitments have been adopted by several cryptocurrencies for hiding transaction amounts. While Pedersen commitments are perfectly hiding in isolation, the cryptocurrency transaction rules can reveal relationships between the amounts hidden in the commitments involved in the transaction. Such relationships can be combined with the public coin creation schedule to provide upper bounds on the number of coins in a commitment. In this paper, we consider the Grin cryptocurrency and derive upper bounds on the number of coins which can be present in regular transaction outputs. In a March 2020 snapshot of the Grin blockchain, we find that out of the 110,149 unspent regular transaction outputs 983 of them have less than 1800 grin (number of coins typically minted in half an hour) stored in them. On the other hand, 95% of the unspent regular transaction outputs in the snapshot have an upper bound which is at least 90% of the total Grin supply at their respective block heights. We conclude that while our method does not violate the confidentiality of the amounts in most of the outputs on the Grin blockchain, the amounts in some outputs can be estimated to be in a narrow range.

This paper exposes a new vulnerability and introducesa corresponding attack, the NoneXistent Name ServerAttack (NXNSAttack), that disrupts and may paralyzethe DNS system making it difficult or impossible for In-ternet users to access websites, web e-mail, online videochats, or any other online resource. The NXNSAttackgenerates a storm of packets between DNS resolvers andDNS authoritative name servers. The storm is producedby the response of resolvers to unrestricted referral re-sponse messages of authoritative name servers. Theattack is significantly more destructive than NXDomainattacks (e.g., the Mirai attack): i) It reaches an am-plification factor of more than 1620x on the numberof packets exchanged by the recursive resolver. ii) Inaddition to the negative cache, the attack also satu-rates the ‘NS’ resolver caches. To mitigate the attackimpact, we propose an enhancement to the recursiveresolver algorithm, MaxFetch(k), that prevents unnec-essary proactive fetches. We implemented MaxFetch(1)mitigation enhancement on a BIND resolver and testedit on real-world DNS query datasets. Our results showthat MaxFetch(1) degrades neither the recursive resolverthroughput nor its latency. Following the discovery of theattack, a responsible disclosure procedure was carriedout, and several DNS vendors and public providers haveissued a CVE and patched their systems.

Privacy-preserving machine learning (PPML) has many applications, from medical image evaluation and anomaly detection to financial analysis. nGraph-HE (Boemer et al., Computing Frontiers'19) enables data scientists to perform private inference of deep learning (DL) models trained using popular frameworks such as TensorFlow. nGraph-HE computes linear layers using the CKKS homomorphic encryption (HE) scheme (Cheon et al., ASIACRYPT'17), and relies on a client-aided model to compute non-polynomial activation functions, such as MaxPool and ReLU, where intermediate feature maps are sent to the data owner to compute activation functions in the clear. This approach leaks the feature maps, from which it may be possible to deduce the DL model weights. As a result, the client-aided model may not be suitable for deployment when the DL model is intellectual property. In this work, we present MP2ML, a machine learning framework which integrates nGraph-HE and the secure two-party computation framework ABY (Demmler et al., NDSS'15), to overcome the limitations of the client-aided model. We introduce a novel scheme for the conversion between CKKS and secure multi-party computation (MPC) to execute DL inference while maintaining the privacy of both the input data and model weights. MP2ML is compatible with popular DL frameworks such as TensorFlow that can infer pre-trained neural networks with native ReLU activations. We benchmark MP2ML on the CryptoNets network with ReLU activations, on which it achieves a throughput of 33.3 images/s and an accuracy of 98.6%. This throughput matches the previous state-of-the-art for hybrid HE-MPC networks from GAZELLE (Juvekar et al., USENIX'18), even though our protocol is more accurate and scalable than GAZELLE.

Nowadays, the resistance against algebraic attacks and fast algebraic attacks are considered as an important cryptographic property for Boolean functions used in stream ciphers. Both attacks are very powerful analysis concepts and can be applied to symmetric cryptographic algorithms used in stream ciphers. The notion of algebraic immunity has received wide attention since it is a powerful tool to measure the resistance of a Boolean function to standard algebraic attacks. Nevertheless, an algebraic tool to handle the resistance to fast algebraic attacks is not clearly identified in the literature. In the current paper, we propose a new parameter to measure the resistance of a Boolean function to fast algebraic attack. We also introduce the notion of fast immunity profile and show that it informs both on the resistance to standard and fast algebraic attacks. Further, we evaluate our parameter for two secondary constructions of Boolean functions. Moreover, A coding-theory approach to the characterization of perfect algebraic immune functions is presented. Via this characterization, infinite families of binary linear complementary dual codes (or LCD codes for short) are obtained from perfect algebraic immune functions. The binary LCD codes presented in this paper have applications in armoring implementations against so-called side-channel attacks (SCA) and fault non-invasive attacks, in addition to their applications in communication and data storage systems.

Secret sharing is a very useful way to maintain secrecy of private data when stored in a distributed way among several nodes. Two significant questions in this area are 1. how to accommodate new nodes and assign shares to the new nodes, the problem becomes harder if the number of joining nodes or the access structure is not known in advance and can be (potentially) unbounded and 2. to reduce the computational complexity of secret sharing schemes. In this paper we propose two new constructions of such secret sharing schemes based on different combinatorial structures. The first construction is based on generalized paths joining the opposite vertices of a hypercube which has been divided into smaller hypercubes. The second construction is a forest- based construction utilizing a dynamic data structure technique known as fractional cascading. The generalized path we call a pavement is new to this paper. Both our constructions use a new secret redistribution scheme to assign and re-assign shares to nodes. Towards the second question we show that allowing certain trade-offs, the constructions are implementable by $AC^0$ circuits which is the lowest complexity class in which secret sharing and reconstruction is possible. To the best of the knowledge of the authors, none of the similar existing schemes (evolving or dynamic) are $AC^0$ computable and this paper for the first time combines the idea of hypercubes and dynamic data structures with secret sharing for preserving long-term confidentiality of secret data.

The common approach in secure channel protocols is to rely on ciphertexts arriving in-order and to close the connection upon any rogue ciphertext. Cryptographic security models for channels generally reflect such design. This is reasonable when running atop lower-level transport protocols like TCP ensuring in-order delivery, as for example is the case with TLS or SSH. However, channels such as QUIC or DTLS which run over a non-reliable transport protocol like UDP, do not---and in fact cannot---close the connection if packets are lost or arrive in a different order. Those protocols instead have to carefully catch effects arising naturally in unreliable networks, usually by using a sliding-window technique where ciphertexts can be decrypted correctly as long as they are not misplaced too far.

To accommodate such handling of unreliable network messages, we introduce a generalized notion of robustness of cryptographic channels. This property can capture unreliable network behavior and guarantees that adversarial tampering cannot hinder ciphertexts that can be decrypted correctly from being accepted. We show that robustness is orthogonal to the common notion of integrity for channels, but together with integrity and chosen-plaintext security it provides a robust analogue of chosen-ciphertext security of channels. We then discuss two particularly interesting targets, namely the packet encryption in the record layer protocols of QUIC and of DTLS 1.3. We show that both protocols achieve the intended level of robust chosen-ciphertext security based on certain properties of their sliding-window techniques and on the underlying AEAD schemes. Notably, the robustness needed in handling unreliable network messages require both record layer protocols to tolerate repeated adversarial forgery attempts, which means we can only establish non-tight security bounds (in terms of AEAD integrity). Our bounds have led the responsible IETF working groups to introduce concrete forgery limits for both protocol drafts.

As the fault based analysis techniques are becoming more and more powerful, there is a need to streamline the existing tools for better accuracy and ease of use. In this regard, we propose a machine learning assisted tool that can be used in the context of a differential fault analysis. In particular, finding the exact fault location by analyzing the XORed output of a stream cipher/ stream cipher based design is somewhat non-trivial. Traditionally, Pearson's correlation coefficient is used for this purpose. We show that a machine learning method is more powerful than the existing correlation coefficient, aside from being simpler to implement. As a proof of concept, we take two variants of Grain-128a (namely a stream cipher, and a stream cipher with authentication), and demonstrate that machine learning can outperform correlation with the same training/testing data. Our analysis shows that the machine learning can be considered as a replacement for the correlation in the future research works.