Elena Andreeva

Assistant Prof. / PhD

Elena Andreeva

My research interests lie in the area of theory and applications of cryptography and more concretely in symmetric cryptography, authenticated encryption, forkciphers, hash functions, key derivation, provable security, privacy-friendly security protocols, and cryptography for blockchains. I am interested in theory and development of provably secure cryptographic designs for secure data communications, storage and private computation.


Previously, I was an Assistant Professor in the Cyber Security Group at DTU, Denmark and a Lecturer in the Cyber Security Research Group at University of Klagenfurt, Austria. Prior to that, I worked as a Research Expert in the COSIC Research Group, KU Leuven, Belgium. My PhD and my Postdoctoral research was also at COSIC and was funded by a PhD and Postdoctoral grants from the Flemish Research Foundation (FWO). I completed my PhD, entitled Domain Extenders for Cryptographic Hash Functions, in 2010 under the supervision of prof. Bart Preneel. I hold a Master’s degree in Computer Science from the University of Saarland, Germany.

More details about my research can be found on my personal webpage https://elenandreeva.github.io.

I am always looking for motivated students! Contact me if you are interested in working with me and have a look at our open positions and thesis opportunities!

Roles
  • Assistant Professor
Publications (created while at TU Wien)
    2023
    • Quantum cryptanalysis of Farfalle and (generalised) key-alternating Feistel networks
      Hodžić, S., Roy, A., & Andreeva, E. (2023). Quantum cryptanalysis of Farfalle and (generalised) key-alternating Feistel networks. Designs, Codes and Cryptography.
      DOI: 10.1007/s10623-023-01305-6 Metadata
      Abstract
      Farfalle is a permutation-based construction for building a pseudorandom function which has been proposed by Bertoni et al. in 2017. In this work, we show that by observing suitable inputs to Farfalle, one can derive various constructions of a periodic function with a period that involves a secret key. As this admits the application of Simon’s algorithm in the so-called Q2 attack model, we further show that in the case when internal rolling function is linear, then the secret key can be extracted under feasible assumptions. Furthermore, using the provided constructions of periodic functions for Farfalle, we show that one can mount forgery attacks on the session-supporting mode for authenticated encryption (Farfalle-SAE) and the synthetic initial value AE mode (Farfalle-SIV). In addition, as the wide block cipher mode Farfalle-WBC is a 4-round Feistel scheme, a quantum distinguisher is constructed in the case when input branches are containing at last two blocks, where length of one block corresponds to the size of a permutation employed in Farfalle (a similar attack can be mounted to Farfalle-WBC-AE). And finally, we consider the problem of extracting a secret round key out of different periods obtained from a (Generalized) Feistel scheme (GFN), which has not been addressed in any of the previous works which consider the application of Simon’s (or Simon-Grover) algorithm to round reduced versions of GFNs. In this part, we assume that the key is added to an input of an inner function utilized in the round function of a given GFN. By applying two different interpolation formulas, we show that one can extract the round key by utilizing amount of different periods which is closely related to the polynomial/algebraic degree of underlying inner function. Our methods can be seen as an extension of existing quantum attacks on key-alternating GFNs based on Simon’s or Simon-Grover algorithms.
    • Let's Go Eevee! A Friendly and Suitable Family of AEAD Modes for IoT-to-Cloud Secure Computation
      Bhati, A. S., Pohle, E., Abidin, A., Andreeva, E., & Preneel, B. (2023). Let’s Go Eevee! A Friendly and Suitable Family of AEAD Modes for IoT-to-Cloud Secure Computation. In CCS ’23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security (pp. 2546–2560). Association for Computing Machinery.
      DOI: 10.1145/3576915.3623091 Metadata
      Abstract
      IoT devices collect privacy-sensitive data, e.g., in smart grids or in medical devices, and send this data to cloud servers for further processing. In order to ensure confidentiality as well as authenticity of the sensor data in the untrusted cloud environment, we consider a transciphering scenario between embedded IoT devices and multiple cloud servers that perform secure multi-party computation (MPC). Concretely, the IoT devices encrypt their data with a lightweight symmetric cipher and send the ciphertext to the cloud servers. To obtain the secret shares of the cleartext message for further processing, the cloud servers engage in an MPC protocol to decrypt the ciphertext in a distributed manner. This way, the plaintext is never exposed to the individual servers. As an important building block in this scenario, we propose a new, provably secure family of lightweight modes for authenticated encryption with associated data (AEAD), called Eevee. The Eevee family has fully parallel decryption, making it suitable for MPC protocols for which the round complexity depends on the complexity of the function they compute. Further, our modes use the lightweight forkcipher primitive that offers fixed-length output expansion and a compact yet parallelizable internal structure. All Eevee members improve substantially over the few available state-of-the-art (SotA) MPC-friendly modes and other standard solutions. We benchmark the Eevee family on a microcontroller and in MPC. Our proposed mode Jolteon (when instantiated with ForkSkinny) provides 1.85x to 3.64x speedup in IoT-encryption time and 3x to 4.5x speedup in both MPC-decryption time and data for very short queries of 8 bytes and, 1.55x to 3.04x and 1.23x to 2.43x speedup, respectively, in MPC-decryption time and data for queries up to 500 bytes when compared against SotA MPC-friendly modes instantiated with SKINNY. We also provide two advanced modes, Umbreon and Espeon, that show a favorable performance-security trade-off with stronger security guarantees such as nonce-misuse security. Additionally, all Eevee members have full n-bit security (where n is the block size of the underlying primitive), use a single primitive and require smaller state and HW area when compared with the SotA modes under their original security settings.
    • A Forkcipher-Based Pseudo-Random Number Generator
      Andreeva, E., & Weninger, A. (2023). A Forkcipher-Based Pseudo-Random Number Generator. In M. Tibouchi & X. Wang (Eds.), Applied Cryptography and Network Security (pp. 3–31).
      DOI: 10.1007/978-3-031-33491-7_1 Metadata
      Abstract
      Good randomness is needed for most cryptographic applications. In practice pseudo-random number generators (PRNGs) are employed. CTR_DRBG is a popular choice and among the recommended PRNGs by NIST. It is defined for use with primitives like AES or TDEA, which are not always suited for lightweight applications. In this work we propose FCRNG, a new PRNG, similar to CTR_DRBG, that is optimized for the lightweight setting (e.g. the Internet of Things). Our FCRNG construction utilizes the expanding and tweakable forkcipher primitive instantiated with ForkSkinny, which was introduced by Andreeva et al. at ASIACRYPT 2019. FCRNG employs internally a forkcipher-based counter-style mode FCTR. We propose two FCTR variants: FCTR-c for optimized speed and FCTR-T for optimized security. We then show that FCRNG with ForkSkinny can be 33% faster than CTR_DRBG when instantiated with the AES blockcipher. FCRNG achieves also a better security bound in the robustness security game - first introduced by Dodis et al. at CCS’13 and now the standard security goal for PRNGs. Contrary to the CRYPTO 2020 security bound by Hoang and Shen established for CTR_DRBG, the security of our construction with FCTR-T does not degrade with the length of the random inputs, nor the amount of requested output pseudorandom bits. FCRNG passes all tests of the NIST test suite for pseudorandom number generators.
    2021
    • 1, 2, 3, Fork: Counter Mode Variants based on a Generalized Forkcipher
      Andreeva, E., Bhati, A. S., Preneel, B., & Vizár, D. (2021). 1, 2, 3, Fork: Counter Mode Variants based on a Generalized Forkcipher. IACR Transactions on Symmetric Cryptology, 2021(3).
      DOI: 10.46586/tosc.v2021.i3.1-35 Metadata
      Abstract
      A multi-forkcipher (MFC) is a generalization of the forkcipher (FC) primitive introduced by Andreeva et al. at ASIACRYPT’19. An MFC is a tweakable cipher that computes s output blocks for a single input block, with s arbitrary but fixed. We define the MFC security in the ind-prtmfp notion as indistinguishability from s tweaked permutations. Generalizing tweakable block ciphers (TBCs, s = 1), as well as forkciphers (s = 2), MFC lends itself well to building simple-to-analyze modes of operation that support any number of cipher output blocks. Our main contribution is the generic CTR encryption mode GCTR that makes parallel calls to an MFC to encrypt a message M. We analyze the set of all 36 “simple and natural” GCTR variants under the nivE security notion by Peyrin and Seurin from CRYPTO’16. Our proof method makes use of an intermediate abstraction called tweakable CTR (TCTR) that captures the core security properties of GCTR common to all variants, making their analyses easier. Our results show that many of the schemes achieve from well beyond birthday bound (BBB) to full n-bit security under nonce respecting adversaries and some even BBB and close to full n-bit security in the face of realistic nonce misuse conditions. We finally present an efficiency comparison of GCTR using ForkSkinny (an MFC with s = 2) with the traditional CTR and the more recent CTRT modes, both are instantiated with the SKINNY TBC. Our estimations show that any GCTR variant with ForkSkinny can achieve an efficiency advantage of over 20% for moderately long messages, illustrating that the use of an efficient MFC with s ≥ 2 brings a clear speed-up.
    • Interpolation Cryptanalysis of Unbalanced Feistel Networks with Low Degree Round Functions
      Andreeva, E., Roy, A., & Sauer, J. F. (2021). Interpolation Cryptanalysis of Unbalanced Feistel Networks with Low Degree Round Functions. In Selected Areas in Cryptography (pp. 273–300). Springer LNCS.
      DOI: 10.1007/978-3-030-81652-0_11 Metadata ⯈Fulltext (preprint)
      Abstract
      In recent years a new type of block ciphers and hash functions over a (large) field, such as MiMC and GMiMC, have been designed. Their security, particularly over a prime field, is mainly determined by algebraic cryptanalysis techniques, such as Gröbner basis and interpolation attacks. In SAC 2019, Li and Preneel presented low memory interpolation attack against the MiMC and Feistel-MiMC designs. In this work we answer the open question posed in their work and show that low memory interpolation attacks can be extended to unbalanced Feistel networks (UFN) with low degree functions, and in particular to the GMiMC design. Our attack applies to UFNs with expanding and contracting round functions keyed either via identical (univariate) or distinct round keys (multivariate). Since interpolation attacks do not necessarily yield the best possible attacks over a binary extension field, we focus our analysis on prime fields Fp . Our next contribution is to develop an improved technique for a more efficient key recovery against UFNs with expanding round function. We show that the final key recovery step can be reduced not only to the gcd but also to the root finding problem. Despite its higher theoretical complexity, we show that our approach has a particularly interesting application on Sponge hash functions based on UFNs, such as GMiMCHash. We illustrate for the first time how our root finding technique can be used to find collision, second preimage and preimage attacks on (reduced round) members of the GMiMCHash family. In addition, we support our theoretical analysis with small-scale experimental results.
    • Compactness of Hashing Modes and Efficiency Beyond Merkle Tree
      Andreeva, E., Bhattacharyya, R., & Roy, A. (2021). Compactness of Hashing Modes and Efficiency Beyond Merkle Tree. In Advances in Cryptology – EUROCRYPT 2021 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part II (pp. 92–123). Springer.
      DOI: 10.1007/978-3-030-77886-6_4 Metadata ⯈Fulltext (preprint)
      Abstract
      We revisit the classical problem of designing optimally efficient cryptographically secure hash functions. Hash functions are traditionally designed via applying modes of operation on primitives with smaller domains. The results of Shrimpton and Stam (ICALP 2008), Rogaway and Steinberger (CRYPTO 2008), and Mennink and Preneel (CRYPTO 2012) show how to achieve optimally efficient designs of 2n-to-n-bit compression functions from non-compressing primitives with asymptotically optimal 2n/2−ϵ -query collision resistance. Designing optimally efficient and secure hash functions for larger domains ( >2n bits) is still an open problem. To enable efficiency analysis and comparison across hash functions built from primitives of different domain sizes, in this work we propose the new compactness efficiency notion. It allows us to focus on asymptotically optimally collision resistant hash function and normalize their parameters based on Stam´s bound from CRYPTO 2008 to obtain maximal efficiency. We then present two tree-based modes of operation as a design principle for compact, large domain, fixed-input-length hash functions. 1. Our first construction is an Augmented Binary Tree (ABR) mode. The design is a (2ℓ+2ℓ−1−1)n -to-n-bit hash function making a total of (2ℓ−1) calls to 2n-to-n-bit compression functions for any ℓ≥2 . Our construction is optimally compact with asymptotically (optimal) 2n/2−ϵ -query collision resistance in the ideal model. For a tree of height ℓ , in comparison with Merkle tree, the ABR mode processes additional (2ℓ−1−1) data blocks making the same number of internal compression function calls. 2. With our second design we focus our attention on the indifferentiability security notion. While the ABR mode achieves collision resistance, it fails to achieve indifferentiability from a random oracle within 2n/3 queries. ABR+ compresses only 1 less data block than ABR with the same number of compression calls and achieves in addition indifferentiability up to 2n/2−ϵ queries. Both of our designs are closely related to the ubiquitous Merkle Trees and have the potential for real-world applicability where the speed of hashing is of primary interest.
    • Optimized Software Implementations for the Lightweight Encryption Scheme ForkAE
      Andreeva, E., Deprez, A., Bermudo Mera, J. M., Karmakar, A., & Purnal, A. (2021). Optimized Software Implementations for the Lightweight Encryption Scheme ForkAE. In Smart Card Research and Advanced Applications (pp. 68–83). Springer.
      DOI: 10.1007/978-3-030-68487-7_5 Metadata ⯈Fulltext (preprint)
      Abstract
      In this work we develop optimized software implementations for ForkAE, a second round candidate in the ongoing NIST lightweight cryptography standardization process. Moreover, we analyze the performance and efficiency of different ForkAE implementations on two embedded platforms: ARM Cortex-A9 and ARM Cortex-M0. First, we study portable ForkAE implementations. We apply a decryption optimization technique which allows us to accelerate decryption by up to 35%. Second, we go on to explore platform-specific software optimizations. In platforms where cache-timing attacks are not a risk, we present a novel table-based approach to compute the SKINNY round function. Compared to the existing portable implementations, this technique speeds up encryption and decryption by 20% and 25%, respectively. Additionally, we propose a set of platform-specific optimizations for processors with parallel hardware extensions such as ARM NEON. Without relying on parallelism provided by long messages (cf. bit-sliced implementations), we focus on the primitive-level ForkSkinny parallelism provided by ForkAE to reduce encryption and decryption latency by up to 30%. We benchmark the performance of our implementations on the ARM Cortex-M0 and ARM Cortex-A9 processors and give a comparison with the other SKINNY-based schemes in the NIST lightweight competition - SKINNY-AEAD and Romulus.
    • Nonce-Misuse Security of the SAEF Authenticated Encryption Mode
      Andreeva, E., Bhati, A. S., & Vizár, D. (2021). Nonce-Misuse Security of the SAEF Authenticated Encryption Mode. In Selected Areas in Cryptography (pp. 512–534). Springer LNCS.
      DOI: 10.1007/978-3-030-81652-0_20 Metadata ⯈Fulltext (preprint)
      Abstract
      ForkAE is a NIST lightweight cryptography candidate that uses the forkcipher primitive in two modes of operation - SAEF and PAEF - optimized for authenticated encryption of the shortest messages. SAEF is a sequential and online AEAD that minimizes the memory footprint compared to its alternative parallel mode PAEF, catering to the most constrained devices. SAEF was proven AE secure against nonce-respecting adversaries. Due to their more acute and direct exposure to device misuse and mishandling, in most use cases of lightweight cryptography, nonce reuse presents a very realistic attack vector. Furthermore, many lightweight applications mandate security for their online AEAD schemes against block-wise adversaries. Surprisingly, a very few NIST lightweight AEAD candidates come with provable guarantees against these security threats. In this work we investigate the provable security guarantees of SAEF when nonces are repeated under a refined version of the notion of online authenticated encryption OAE given by Fleischmann et al. in 2012. Using the coefficient H technique we show that, with no modifications, SAEF is OAE secure up to the birthday security bound, i.e., up to 2n/2 processed blocks of data, where n is the block size of the forkcipher. The implications of our work is that SAEF is safe to use in a block-wise fashion, and that if nonces get repeated, this has no impact on ciphertext integrity and confidentiality only degrades by a limited extent up to repetitions of common message prefixes.
    2019
    • Forkcipher: A New Primitive for Authenticated Encryption of Very Short Messages
      Andreeva, E., Lallemand, V., Purnal, A., Reyhanitabar, R., Roy, A., & Vizár, D. (2019). Forkcipher: A New Primitive for Authenticated Encryption of Very Short Messages. In Advances in Cryptology – ASIACRYPT 2019 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8–12, 2019, Proceedings, Part II (pp. 153–182). Springer LNCS.
      DOI: 10.1007/978-3-030-34621-8_6 Metadata ⯈Fulltext (preprint)
      Abstract
      Highly efficient encryption and authentication of short messages is an essential requirement for enabling security in constrained scenarios such as the CAN FD in automotive systems (max. message size 64 bytes), massive IoT, critical communication domains of 5G, and Narrowband IoT, to mention a few. In addition, one of the NIST lightweight cryptography project requirements is that AEAD schemes shall be "optimized to be efficient for short messages (e.g., as short as 8 bytes)". In this work we introduce and formalize a novel primitive in symmetric cryptography called forkcipher. A forkcipher is a keyed primitive expanding a fixed-lenght input to a fixed-length output. We define its security as indistinguishability under a chosen ciphertext attack (for n-bit inputs to 2n-bit outputs). We give a generic construction validation via the new iterate-fork-iterate design paradigm. We then propose ForkSkinny as a concrete forkcipher instance with a public tweak and based on SKINNY: a tweakable lightweight cipher following the TWEAKEY framework. We conduct extensive cryptanalysis of ForkSkinny against classical and structure-specific attacks. We demonstrate the applicability of forkciphers by designing three new provably-secure nonce-based AEAD modes which offer performance and security tradeoffs and are optimized for efficiency of very short messages. Considering a reference block size of 16 bytes, and ignoring possible hardware optimizations, our new AEAD schemes beat the best SKINNY-based AEAD modes. More generally, we show forkciphers are suited for lightweight applications dealing with predominantly short messages, while at the same time allowing handling arbitrary messages sizes. Furthermore, our hardware implementation results show that when we exploit the inherent parallelism of ForkSkinny we achieve the best performance when directly compared with the most efficient mode instantiated with SKINNY.