@inproceedings {27709,
title = {Boolean Polynomials, BDDs and CRHS Equations {\textendash} Connecting the Dots with CryptaPath},
journal = {Selected Areas in Cryptography},
volume = {12804},
year = {2021},
month = {07/2021},
pages = {229-251},
publisher = { Springer},
address = {Cham},
abstract = {When new symmetric-key ciphers and hash functions are proposed they are expected to document resilience against a number of known attacks. Good, easy to use tools may help designers in this process and give improved cryptanalysis. In this paper we introduce CryptaPath, a tool for doing algebraic cryptanalysis which utilizes Compressed Right-Hand Side (CRHS) equations to attack SPN ciphers and sponge constructions. It requires no previous knowledge of CRHS equations to be used, only a reference implementation of a primitive.
The connections between CRHS equations, binary decision diagrams and Boolean polynomials have not been described earlier in literature. A comprehensive treatment of these relationships is made before we explain how CryptaPath works. We then describe the process of solving CRHS equation systems while introducing a new operation, dropping variables.},
keywords = {algebraic cryptanalysis, binary decision diagram, block cipher, equation system, Open Source, tool},
isbn = {978-3-030-81651-3},
doi = {https://doi.org/10.1007/978-3-030-81652-0_9},
url = {https://link.springer.com/chapter/10.1007/978-3-030-81652-0_9},
author = {John Petter {Indr{\o}y} and Costes, Nicolas and Raddum, H{\r a}vard},
editor = {O., Dunkelman and Jr. M.J. {Jacobson} and C., O{\textquoteright}Flynn}
}
@inproceedings {27710,
title = {Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2},
journal = {Eurocrypt},
volume = {12697},
year = {2021},
month = {06/2021},
pages = {155-183},
publisher = {springer},
abstract = {This paper presents the first publicly available cryptanalytic attacks on the GEA-1 and GEA-2 algorithms. Instead of providing full 64-bit security, we show that the initial state of GEA-1 can be recovered from as little as 65 bits of known keystream (with at least 24 bits coming from one frame) in time 2^{40} GEA-1 evaluations and using 44.5 GiB of memory.
The attack on GEA-1 is based on an exceptional interaction of the deployed LFSRs and the key initialization, which is highly unlikely to occur by chance. This unusual pattern indicates that the weakness is intentionally hidden to limit the security level to 40 bit by design.
In contrast, for GEA-2 we did not discover the same intentional weakness. However, using a combination of algebraic techniques and list merging algorithms we are still able to break GEA-2 in time 2^{45.1} GEA-2 evaluations. The main practical hurdle is the required knowledge of 1600 bytes of keystream.},
keywords = {algebraic attacks, GEA, GPRS Encryption, Stream Cipher},
isbn = {978-3-030-77885-9},
doi = {https://doi.org/10.1007/978-3-030-77886-6_6},
url = {https://link.springer.com/chapter/10.1007/978-3-030-77886-6_6},
author = {Derbez, Patrick and Leander, Gregor and Leurent, Ga{\"e}tan and Raddum, H{\r a}vard and Rotella, Yann and Rupprecht, David and Beierle, Christof and Stennes, Lukas},
editor = {Standaert FX. Cantea {A.}}
}
@inproceedings {28253,
title = {FASTA {\textendash} a stream cipher for fast FHE evaluation},
journal = {CT-RSA},
year = {2021},
publisher = { Springer},
address = {Cham},
abstract = {In this paper we propose Fasta, a stream cipher design optimised for implementation over popular fully homomorphic encryption schemes. A number of symmetric encryption ciphers have been recently proposed for FHE applications, e.g. the block cipher LowMC, and the stream ciphers Rasta (and variants), FLIP and Kreyvium. The main design criterion employed in these ciphers has typically been to minimise the multiplicative complexity of the algorithm. However, other aspects affecting their efficient evaluation over common FHE libraries are often overlooked, compromising their real-world performance. Whilst Fasta may also be considered as a variant of Rasta, it has its parameters and linear layer especially chosen to allow efficient implementation over the BGV scheme, particularly as implemented in the HElib library. This results in a speedup by a factor of 25 compared to the most efficient publicly available implementation of Rasta.\ Fasta{\textquoteright}s target is BGV, as implemented in HElib. However the design ideas introduced in the cipher could also be potentially employed to achieve improvements in the homomorphic evaluation in other popular FHE schemes/libraries. We do consider such alternatives in this paper (e.g. BFV and BGVrns, as implemented in SEAL and PALISADE), but argue that, unlike BGVin HElib, it is more challenging to make use of their parallelism in a Rasta-like stream cipher design.},
keywords = {Homomorphic Encryption, Hybrid Encryption, secret-key cryptography, Stream Ciphers},
author = {Cid, Carlos and John Petter {Indr{\o}y} and Raddum, H{\r a}vard},
editor = {Galbraith, Steven}
}
@inproceedings {27900,
title = {A Practical Adaptive Key Recovery Attack on the LGM (GSW-like) Cryptosystem},
journal = {International Conference on Post-Quantum Cryptography},
volume = {12841},
year = {2021},
month = {07/2021},
pages = {483-498},
publisher = { Springer},
abstract = {We present an adaptive key recovery attack on the leveled homomorphic encryption scheme suggested by Li, Galbraith and Ma (Provsec 2016), which itself is a modification of the GSW cryptosystem designed to resist key recovery attacks by using a different linear combination of secret keys for each decryption. We were able to efficiently recover the secret key for a realistic choice of parameters using a statistical attack. In particular, this means that the Li, Galbraith and Ma strategy does not prevent adaptive key recovery attacks.},
keywords = {GSW, Key recovery, Somewhat homomorphic encryption, Statistical attack},
isbn = {978-3-030-81292-8},
doi = {https://doi.org/10.1007/978-3-030-81293-5_25},
url = {https://link.springer.com/chapter/10.1007/978-3-030-81293-5_25},
author = {Fauzi, Prastudy and Martha Norberg {Hovd} and Raddum, H{\r a}vard},
editor = {Tillich JP. Cheon {J.H.}}
}
@inproceedings {27134,
title = {Cryptanalysis of the Multivariate Encryption Scheme EFLASH},
journal = {RSA Conference Cryptographers{\textquoteright} Track 2020},
volume = {12006},
year = {2020},
month = {02/2020},
pages = {85-105},
publisher = { Springer},
address = {Lecture Notes in Computer Science},
abstract = {EFLASH is a multivariate public-key encryption scheme proposed by Cartor and Smith-Tone at SAC 2018. In this paper we investigate the hardness of solving the particular equation systems arising from EFLASH, and show that the solving degree for these types of systems is much lower than estimated by the authors. We show that a Gr{\"o}bner basis algorithm will produce degree fall polynomials at a low degree for EFLASH systems. In particular we are able to accurately predict the number of these polynomials occurring at step degrees 3 and 4 in our attacks. We performed several experiments using the computer algebra system MAGMA, which indicate that the solving degree is at most one higher than the one where degree fall polynomials occur; moreover, our experiments show that whenever the predicted number of degree fall polynomials is positive, it is exact. Our conclusion is that EFLASH does not offer the level of security claimed by the designers. In particular, we estimate that the EFLASH version with 80-bit security parameters offers at most 69 bits of security.},
isbn = {978-3-030-40186-3},
author = {{\O}ygarden, Morten and Felke, Patrick and Raddum, H{\r a}vard and Cid, Carlos}
}
@inproceedings {27705,
title = {Graphs and Self-dual additive codes over GF(4)},
journal = {The Eleventh International Workshop on Coding and Cryptography},
year = {2019},
abstract = {We initiate the study of self-dual codes over GF(4) whose corresponding graphs have fixed rankwidth. We show that by combining the structural properties of rankwidth 1 graphs, the classification of corresponding codes becomes significantly faster.
We give a new algorithm for computing weight enumerators using Binary Decision Diagrams (BDD), which has similar complexity to brute force O(2^k) but has the benefit that we automatically get complexity O(2^min{k,n-k}) (for k > n/2) without needing to consider the dual code.
We show that the minimum distance of a code is at least 3 if and only if the corresponding graph does not contain any pendant vertex or any twin-pairs. We also give an algorithm for computing an approximate minimum distance in codes corresponding to general graphs.},
keywords = {binary decision diagram, Minimum Distance, Rankwidth, Self-dual, Stabilizer Code},
author = {Kumar, Mithilesh and Varadharajan, Srimathi and Raddum, H{\r a}vard}
}
@article {27708,
title = {Reducing Lattice Enumeration Search Trees},
journal = {Infocommunications Journal},
volume = {11},
year = {2019},
month = {12/2019},
pages = {8-16},
publisher = {The scientific association for infocommunications},
address = {Budapest, Hungary},
abstract = {We revisit the standard enumeration algorithm for finding the shortest vectors in a lattice, and study how the number of nodes in the associated search tree can be reduced. Two approaches for reducing the number of nodes are suggested. First we show that different permutations of the basis vectors have a big effect on the running time of standard enumeration, and give a class of permutations that give relatively few nodes in the search tree. This leads to an algorithm called hybrid enumeration that has a better running time than standard enumeration when the lattice is large. Next we show that it is possible to estimate the signs of the coefficients yielding a shortest vector, and that a pruning strategy can be based on this fact. Sign-based pruning gives fewer nodes in the search tree, and never missed the shortest vector in the experiments we did.},
keywords = {enumeration, Lattices, pruning, SVP problem},
issn = {2061-2079},
doi = {10.36244/ICJ.2019.4.2},
author = {Kumar, Mithilesh and Raddum, H{\r a}vard and Varadharajan, Srimathi}
}
@article {Greve2019,
title = {Solving non-linear Boolean equation systems by variable elimination},
journal = {Applicable Algebra in Engineering, Communication and Computing},
year = {2019},
month = {Aug},
publisher = { Springer},
abstract = {In this paper we study Boolean equation systems, and how to eliminate variables from them while bounding the degree of polynomials produced. A procedure for variable elimination is introduced, and we relate the techniques to Gr{\"o}bner bases and XL methods. We prove that by increasing the degree of the polynomials in the system by one for each variable eliminated, we preserve the solution space, provided that the system satisfies a particular condition. We then estimate how many variables we need to eliminate in order to solve the resulting system by re-linearization, and show that we get complexities lower than the trivial brute-force {\$}{\$}{\backslash}mathcal {\O{\}(2^n){\$}{\$}O(2n)when the system is overdetermined.},
issn = {1432-0622},
doi = {10.1007/s00200-019-00399-7},
url = {https://doi.org/10.1007/s00200-019-00399-7},
author = {Greve, Bj{\o}rn and Ytrehus, {\O}yvind and Raddum, H{\r a}vard and Fl{\o}ystad, Gunnar}
}
@inproceedings {26353,
title = {Definitions for Plaintext-Existence Hiding in Cloud Storage},
journal = {Proceedings of the 13th International Conference on Availability, Reliability and Security},
year = {2018},
publisher = {ACM Press},
address = {New York, NY, USA},
abstract = {Cloud storage services use deduplication for saving bandwidth and storage. An adversary can exploit side-channel information in several attack scenarios when deduplication takes place at the client side, leaking information on whether a specific plaintext exists in the cloud storage. Generalising existing security definitions, we introduce formal security games for a number of possible adversaries in this domain, and show that games representing all natural adversarial behaviors are in fact equivalent. These results allow users and practitioners alike to accurately assess the vulnerability of deployed systems to this real-world concern.},
keywords = {Cloud based storage, information systems, security and privacy},
isbn = {9781450364485},
doi = {10.1145/323083310.1145/3230833.3234515},
url = {http://dl.acm.org/citation.cfm?doid=3230833http://dl.acm.org/citation.cfm?doid=3230833.3234515http://dl.acm.org/ft_gateway.cfm?id=3234515\&ftid=1993395\&dwn=1},
author = {Boyd, Colin and Gareth T. {Davies} and Gj{\o}steen, Kristian and Raddum, H{\r a}vard and Toorani, Mohsen}
}
@article {26355,
title = {Factorization using binary decision diagrams},
journal = {Cryptography and Communications},
volume = {11},
year = {2018},
month = {2018},
pages = {1-18},
publisher = { Springer},
abstract = {We address the factorization problem in this paper: Given an integer\ N=pq, find two factors\ p\ and\ q\ of\ N\ such that\ p\ and\ q\ are of same bit-size. When we say integer multiplication of\ N, we mean expressing\ N\ as a product of two factors\ p\ and\ q\ such that\ p\ and\ q\ are of\ same bit-size. We work on this problem in the light of Binary Decision Diagrams (BDD). A Binary Decision Diagram is an acyclic graph which can be used to represent Boolean functions. We represent integer multiplication of\ N\ as product of factors\ p\ and\ q\ using a BDD. Using various operations on the BDD we present an algorithm for factoring\ N. All calculations are done over\ GF(2). We show that the number of nodes in the constructed BDD is\ O(n3)\ where\ n\ is the number of bits in\ p\ or\ q. We do factoring experiments for the case when\ p\ and\ q\ are primes as in the case of RSA modulus\ N, and report on the observed complexity. The multiplication of large RSA numbers (that cannot be factored fast in practice) can still be easily represented as a BDD.},
keywords = {Binary decision diagrams, Integer factorization, RSA},
issn = {1936-2447},
doi = {10.1007/s12095-018-0304-7},
url = {https://link.springer.com/article/10.1007/s12095-018-0304-7},
author = {Raddum, H{\r a}vard and Varadharajan, Srimathi}
}
@article {26351,
title = {MRHS solver based on linear algebra and exhaustive search},
journal = {Journal of Mathematical Cryptology},
volume = {12},
year = {2018},
month = {09/2018},
pages = {143-157},
publisher = {De Gruyter},
abstract = {We show how to build a binary matrix from the MRHS representation of a symmetric-key cipher. The matrix contains the cipher represented as an equation system and can be used to assess a cipher{\textquoteright}s resistance against algebraic attacks. We give an algorithm for solving the system and compute its complexity. The complexity is normally close to exhaustive search on the variables representing the user-selected key. Finally, we show that for some variants of LowMC, the joined MRHS matrix representation can be used to speed up regular encryption in addition to exhaustive key search.},
keywords = {algebraic cryptanalysis, LowMC, MRHS},
issn = {1862-2976},
doi = {https://doi.org/10.1515/jmc-2017-0005},
url = {https://www.degruyter.com/view/j/jmc.2018.12.issue-3/jmc-2017-0005/jmc-2017-0005.xml?format=INT},
author = {Raddum, H{\r a}vard and Zajac, Pavol}
}
@inproceedings {26354,
title = {Security Notions for Cloud Storage and Deduplication},
journal = {ProvSec 2018: Provable Security},
number = {11192},
year = {2018},
pages = {347 - 365},
publisher = {Springer International Publishing},
address = {Switzerland},
abstract = {Cloud storage is in widespread use by individuals and enterprises but introduces a wide array of attack vectors. A basic step for users is to encrypt their data, yet it is not obvious what security properties are required for such encryption. Furthermore, cloud storage providers often use techniques such as data deduplication for improving efficiency which restricts the application of semantically-secure encryption. Generic security goals and attack models have thus far proved elusive: primitives are considered in isolation and protocols are often proved secure under ad hoc models for restricted classes of adversaries.We formally model natural security notions for cloud storage and deduplication using a generic syntax for storage systems. We define security notions for confidentiality and integrity in encrypted cloud storage and determine relations between these notions. We show how to build cloud storage systems that satisfy our defined security notions using standard cryptographic components.},
isbn = {978-3-030-01445-2},
issn = {0302-9743},
doi = {10.1007/978-3-030-01446-9_20},
url = {https://link.springer.com/chapter/10.1007/978-3-030-01446-9_20},
author = {Raddum, H{\r a}vard and Toorani, Mohsen and Gj{\o}steen, Kristian and Boyd, Colin and Gareth T. {Davies}},
editor = {Baek, J.}
}
@article {24997,
title = {Cryptanalysis of 6-round PRINCE using 2 Known Plaintexts},
journal = {Cryptography and Communications},
year = {2017},
publisher = { Springer},
abstract = {In this paper we focus on the PRINCE block cipher reduced to 6 rounds, with two known plaintext/ciphertext pairs. We develop two attacks on 6-round PRINCE based on accelerated exhaustive search, one with negligible memory usage and one having moderate memory requirements. The time complexity for the first attack is 2^{96.78} encryptions. Time complexity for the second attack depends on the implementation, but can be argued to be approximately 2^{89} for a normal PC. The memory consumption of the second attack is less than 200MB and so is not a restricting factor in a real-world setting.},
keywords = {exhaustive search, lightweight cipher, PRINCE},
issn = {1936-2447},
author = {Rasoolzadeh, Shahram and Raddum, H{\r a}vard}
}
@inproceedings {24998,
title = {Faster Key Recovery Attack on Round-Reduced PRINCE},
journal = {LightSec 2016},
volume = {10098},
year = {2017},
month = {03/2017},
pages = {3-17},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {We introduce a new technique for doing the key recovery part of an integral or higher order differential attack. This technique speeds up the key recovery phase significantly and can be applied to any block cipher with small S-boxes. We show several properties of this technique, then apply it to PRINCE and report on the improvements in complexity from earlier integral and higher order differential attacks on this cipher. Our attacks on 4 and 6 rounds were the fastest and the winner of PRINCE Challenge\&$\#$39;s last round in the category of chosen plaintext attack.},
keywords = {block cipher, higher-order differential, integral, key recovery attack, lightweight, PRINCE},
isbn = {978-3-319-55714-4},
doi = {10.1007/978-3-319-55714-4_1},
url = {https://link.springer.com/chapter/10.1007/978-3-319-55714-4_1},
author = {Rasoolzadeh, Shahram and Raddum, H{\r a}vard}
}
@article {24999,
title = {Improved Multi-Dimensional Meet-in-the-Middle Cryptanalysis of KATAN},
journal = {Tatra Mountains Mathematical Publications},
volume = {67},
year = {2017},
pages = {149-166},
publisher = {Tatra Mountains Mathematical Publications},
abstract = {We study multidimensional meet-in-the-middle attacks on the KATAN block cipher family. Several improvements to the basic attacks are ex- plained. The most noteworthy of these is the technique of guessing only non- linearly involved key bits, which reduces the search space by a significant fac- tor. The optimization decreases the complexity of multidimensional meet-in-the- -middle attacks, allowing more rounds of KATAN to be efficiently attacked than previously reported.},
keywords = {block cipher, KATAN, lightweight, Meet-in-the-Middle, Reducing complexity},
issn = {1338 {\textendash} 9750},
doi = {10.1515/tmmp-2016-0037},
author = {Rasoolzadeh, Shahram and Raddum, H{\r a}vard}
}
@inproceedings {RRafricacrypt,
title = {Cryptanalysis of PRINCE with Minimal Data},
journal = {Africacrypt 2016},
volume = {9646},
year = {2016},
month = {04/2016},
pages = {109-126},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {We investigate two attacks on the PRINCE block cipher in the most realistic scenario, when the attacker only has a minimal amount of known plaintext available. The first attack is called Accelerated Exhaustive Search, and is able to recover the key for up to the full 12-round PRINCE with a complexity slightly lower than the security claim given by the designers. The second attack is a meet-in-the-middle attack, where we show how to successfully attack 8- and 10-round PRINCE with only two known plaintext/ciphertext pairs. Both attacks take advantage of the fact that the two middle rounds in PRINCE are unkeyed, so guessing the state before the first middle round gives the state after the second round practically for free. These attacks are the fastest until now in the known plaintext scenario for the 8 and 10 reduced-round versions and the full 12-round of PRINCE.\ },
keywords = {Cryptanalysis, exhaustivesearch, lightweight cipher, meet- in-the-middle, PRINCE},
isbn = {978-3-319-31516-4},
issn = {0302-9743},
doi = {10.1007/978-3-319-31517-1_6},
url = {http://link.springer.com/chapter/10.1007/978-3-319-31517-1_6},
author = {Rasoolzadeh, Shahram and Raddum, H{\r a}vard}
}
@inproceedings {23487,
title = {Algebraic Analysis of the Simon Block Cipher Family},
journal = {LatinCrypt 2015},
volume = {9230},
year = {2015},
pages = {157 - 169},
publisher = {Lecture Notes in Computer Science, Springer.Verlag},
edition = {Lecture Notes in Computer Science},
abstract = {This paper focuses on algebraic attacks on the Simon family of block ciphers. We construct equation systems using multiple plaintext/ciphertext pairs, and show that many variables in the cipher states coming from different plaintexts are linearly related. A simple solving algorithm exploiting these relations is developed and extensively tested on the different Simon variants, giving efficient algebraic attacks on up to 16 rounds of the largest Simon variants.},
keywords = {algebraic attack, block cipher, equation system, Simon},
isbn = {978-3-319-22173-1},
issn = {0302-9743},
author = {Raddum, H{\r a}vard}
}
@inproceedings {23484,
title = {Algebraic Attacks Using Binary Decision Diagrams},
journal = {BalkanCryptSec 2014},
volume = {9024},
year = {2015},
month = {07/2015},
pages = {40 - 54},
publisher = {Lecture Notes in Computer Science, Springer.Verlag},
abstract = {Algebraic attacks have been developed against symmetric primitives during the last decade. In this paper we represent equation systems using binary decision diagrams, and explain techniques for solving them. Next, we do experiments with systems describing reduced versions of DES and AES, as well as systems for the problem of determining EA-equivalence. We compare our results against Gröbner basis and CryptoMiniSat.},
keywords = {algebraic attack, binary decision diagram, block cipher, symmetric primitives},
isbn = {978-3-319-21356-9},
issn = {0302-9743},
doi = {10.1007/978-3-319-21356-9_4},
url = {http://link.springer.com/chapter/10.1007/978-3-319-21356-9_4},
author = {Raddum, H{\r a}vard and Kazymyrov, Oleksandr}
}
@article {23486,
title = {Influence of addition modulo 2^n on algebraic attacks},
journal = {Cryptography and Communications},
volume = {8},
year = {2015},
month = {05/2015},
pages = {277-289},
publisher = {Springer Verlag},
abstract = {Many modern ciphers have a substitution-permutation (SP) network as a main component. This design is well researched in relation to Advanced Encryption Standard (AES). One of the ways to improve the security of cryptographic primitives is the use of additional nonlinear layers. However, this replacement may not have any effect against particular cryptanalytic attacks. In this paper we use algebraic attacks to analyze an SP network with addition modulo 2^n as the key mixing layer. In particular, we show how to reduce the number of intermediate variables in round functions based on SP networks. We also apply the proposed method to the GOST 28147-89 block cipher that allows us to break reduced 8- and 14-round versions with complexity at most 2^{155} and 2^{215.4}, respectively.},
keywords = {Addition modulo 2^n, algebraic attack, binary decision diagram, block cipher},
issn = {1936-2455},
doi = {10.1007/s12095-015-0136-7},
url = {http://link.springer.com/article/10.1007/s12095-015-0136-7},
author = {Kazymyrov, Oleksandr and Oliynykov, Roman and Raddum, H{\r a}vard}
}
@misc {24095,
title = {D{\o}mt til d{\r a}rlig sikkerhet},
howpublished = {Chronicle in Bergens Tidende},
year = {2014},
month = {02/2014},
publisher = {Bergens Tidende},
type = {Chronicle},
address = {Bergen},
abstract = {SIKKERHET P{\r A} NETT: Ville vi akseptert at postmannen {\r a}pnet alle brevene v{\r a}re og la innholdet i postkassen?},
url = {http://www.bt.no/meninger/kronikk/Domt-til-darlig-sikkerhet-3055677.html},
author = {Raddum, H{\r a}vard and Kjell J{\o}rgen {Hole}}
}
@misc {24096,
title = {Snowden-stormen har stilnet. Hva n{\r a}?},
howpublished = {Chronicle on NRK Ytring},
year = {2014},
month = {04/2014},
publisher = {Norsk Rikskringkasting},
type = {Chronicle},
address = {Oslo},
abstract = {USA ser ikke ut til {\r a} ville innskrenke overv{\r a}kningen. Supervarsleren Edward Snowden har likevel n{\r a}dd sitt uttalte m{\r a}l.},
url = {http://www.nrk.no/ytring/snowden-stormen-har-stilnet-1.11633844},
author = {Raddum, H{\r a}vard}
}
@inproceedings {24094,
title = {Solving Compressed Right Hand Side Equation Systems with Linear Absorption},
journal = {7th International Conference on Sequences and Their Applications, SETA 2012},
volume = {7280},
year = {2012},
month = {06/2012},
pages = {291-302},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {In this paper we describe an approach for solving complex multivariate equation systems related to algebraic cryptanalysis. The work uses the newly introduced Compressed Right Hand Sides (CRHS) representation, where equations are represented using Binary Decision Diagrams (BDD). The paper introduces a new technique for manipulating a BDD, similar to swapping variables in the well-known sifting-method. Using this technique we develop a new solving method for CRHS equation systems. The new algorithm is successfully tested on systems representing reduced variants of Trivium.
},
keywords = {algebraic cryptanalysis, BDD, multivariate equation system, Trivium},
isbn = {978-3-642-30614-3},
issn = {0302-9743},
doi = {10.1007/978-3-642-30615-0_27},
url = {http://link.springer.com/chapter/10.1007/978-3-642-30615-0_27},
author = {Thorsten Ernst {Schilling} and Raddum, H{\r a}vard}
}
@inproceedings {24093,
title = {Analysis of Trivium Using Compressed Right Hand Side Equations},
journal = {14th International Conference on Information Security and Cryptology - ICISC 2011},
volume = {7259},
year = {2011},
month = {12/2011},
pages = {18-32},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {We study a new representation of non-linear multivariate equations for algebraic cryptanalysis. Using a combination of multiple right hand side equations and binary decision diagrams, our new representation allows a very efficient conjunction of a large number of separate equations. We apply our new technique to the stream cipher Trivium and variants of Trivium reduced in size. By merging all equations into one single constraint, manageable in size and processing time, we get a representation of the Trivium cipher as one single equation.},
keywords = {algebraic cryptanalysis, BDD, multivariate equation system, Trivium},
isbn = {978-3-642-31911-2},
issn = {0302-9743},
doi = {10.1007/978-3-642-31912-9_2},
url = {http://link.springer.com/chapter/10.1007/978-3-642-31912-9_2},
author = {Thorsten Ernst {Schilling} and Raddum, H{\r a}vard}
}
@misc {24092,
title = {Tutorial Paper on Quantitative Risk Assessment},
howpublished = {Norsk Informasjonssikkerhetskonferanse (NISK) 2011, Troms{\o}},
year = {2011},
type = {Conference presentation},
abstract = {This paper shows how to carry out a quantitative risk assessment, describing how each step in the process is carried out. We use the grade management system at the University of Bergen as a case study, evaluating the risk of wrong grades ending up in the university grade database.},
url = {http://entrance-exam.net/forum/attachments/private-sector-jobs/147807d1397035773-financial-management-risk-management-papers-last-10-years-risk_management_tutorial.pdf},
author = {Mohammad Reza Sohiz {Abyaneh} and Seyed Mehdi Moha {Hassanzadeh} and Raddum, H{\r a}vard}
}
@misc {24091,
title = {Coercion-Resistant Receipts in Electronic Elections},
howpublished = {Norsk Informasjonssikkerhetskonferanse, NISK 2010, Gj{\o}vik},
year = {2010},
type = {Conference presentation},
abstract = {Several suggested Internet-based electronic voting systems provide the voters with receipts to prove that their votes were counted. Unfortunately, these receipts strengthen an adversary{\textquoteright}s ability to coerce voters. This paper proposes a technique for generating receipts which gives voters a high degree of certainty their votes were counted, but without helping a coercer.},
author = {Raddum, H{\r a}vard}
}
@inproceedings {24088,
title = {Security Analysis of Mobile Phones Used as OTP Generators},
journal = {International Workshop on Security Theory and Practice, WISTP 2010},
volume = {6033},
year = {2010},
month = {04/2010},
pages = {324-331},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {The Norwegian company Encap has developed protocols enabling individuals to use their mobile phones as one-time password (OTP) generators. An initial analysis of the protocols reveals minor security flaws. System-level testing of an online bank utilizing Encap\’s solution then shows that several attacks allow a malicious individual to turn his own mobile phone into an OTP generator for another individual\’s bank account. Some of the suggested countermeasures to thwart the attacks are already incorporated in an updated version of the online banking system.},
isbn = {978-3-642-12367-2},
issn = {0302-9743},
doi = {10.1007/978-3-642-12368-9_26},
url = {http://link.springer.com/chapter/10.1007/978-3-642-12368-9_26},
author = {Raddum, H{\r a}vard and Lars Hopland {Nest{\r a}s} and Kjell J{\o}rgen {Hole}}
}
@inproceedings {24089,
title = {Solving Equation Systems by Agreeing and Learning},
journal = {Third International Workshop on the Arithmetic of Finite Fields, WAIFI 2010},
volume = {6087},
year = {2010},
month = {06/2010},
pages = {151-165},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {We study sparse non-linear equation systems defined over a finite field. Representing the equations as symbols and using the Agreeing algorithm we show how to learn and store new knowledge about the system when a guess-and-verify technique is used for solving. Experiments are then presented, showing that our solving algorithm compares favorably to MiniSAT in many instances.},
keywords = {agreeing, dynamic learning, multivariate equation system, SAT-solving},
isbn = {978-3-642-13796-9},
issn = {0302-9743},
doi = {10.1007/978-3-642-13797-6_11},
url = {http://link.springer.com/chapter/10.1007/978-3-642-13797-6_11},
author = {Thorsten Ernst {Schilling} and Raddum, H{\r a}vard}
}
@article {24090,
title = {The Zodiac Killer Ciphers},
journal = {Tatra Mountains Mathematical Publications},
volume = {45},
year = {2010},
pages = {75-91},
publisher = {Tatra Mountains Mathematical Publications},
abstract = {We describe the background of the Zodiac killer{\textquoteright}s cipher, and present a strategy for how to attack the unsolved Z340 cipher. We present evidence that there is a high degree of non-randomness in the sequence of ciphertext symbols in this cipher, suggesting it has been constructed in a systematic way. Next, we use this information to design a tool for solving the Zodiac ciphers. Using this tool we are able to re-solve the known Z408 cipher.},
doi = {10.2478/v10127-010-0007-8},
url = {http://www.sav.sk/journals/uploads/0317152012ra-sy.pdf},
author = {Raddum, H{\r a}vard and Sys, Marek}
}
@inproceedings {24085,
title = {Algebraic Analysis of LEX},
journal = {Australasian Information Security Conference, AISC2009},
volume = {98},
year = {2009},
pages = {33-45},
publisher = {ACS},
abstract = {LEX is a stream cipher that progressed to Phase 3 of the eSTREAM stream cipher project. In this paper, we show that the security of LEX against algebraic attacks relies on a small equation system not being solvable faster than exhaustive search. We use the byte leakage in LEX to construct a system of 21 equations in 17 variables. This is very close to the require- ment for an efficient attack, i.e. a system containing 16 variables. The system requires only 36 bytes of keystream, which is very low.},
keywords = {Advanced Encryption Standard, LEX, Stream Cipher},
isbn = {978-1-920682-79-8},
issn = {1445-1336},
url = {http://crpit.com/abstracts/CRPITV98RezaZaba.html},
author = {Muhammad Reza {Z{\textquoteright}aba} and Raddum, H{\r a}vard and Simpson, Leonie and Dawson, Ed and Henricksen, Matt and Wong, Kenneth}
}
@misc {24243,
title = {N{\r a}r folk stemmer hjemme},
howpublished = {Feature article in HUBRO},
year = {2009},
author = {Raddum, H{\r a}vard and Nestas, L.H. and Kjell J{\o}rgen {Hole}}
}
@inproceedings {24083,
title = {Bit-Pattern Based Integral Attack},
journal = {Fast Software Encryption, FSE 2008},
volume = {5086},
year = {2008},
month = {02/2008},
pages = {363-381},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {Integral attacks are well-known to be effective against byte-based block ciphers. In this document, we outline how to launch integral attacks against bit-based block ciphers. This new type of integral attack traces the propagation of the plaintext structure at bit-level by incorporating bit-pattern based notations. The new notation gives the attacker more details about the properties of a structure of cipher blocks. The main difference from ordinary integral attacks is that we look at the pattern the bits in a specific position in the cipher block has through the structure. The bit-pattern based integral attack is applied to Noekeon, Serpent and\ present\ reduced up to 5, 6 and 7 rounds, respectively. This includes the first attacks on Noekeon and\ present\ using integral cryptanalysis. All attacks manage to recover the full subkey of the final round.\ },
keywords = {block ciphers, integral cryptanalysis, Noekeon, Present, Serpent},
isbn = {978-3-540-71038-7},
issn = {0302-9743},
doi = {10.1007/978-3-540-71039-4_23},
url = {http://link.springer.com/chapter/10.1007/978-3-540-71039-4_23},
author = {Muhammad Reza {Z{\textquoteright}aba} and Raddum, H{\r a}vard and Henricksen, Matt and Dawson, Ed}
}
@inproceedings {24084,
title = {On the Number of Linearly Independent Equations Generated by XL},
journal = {Sequences and Their Applications, SETA 2008},
volume = {5203},
year = {2008},
month = {09/2008},
pages = {239-251},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {Solving multivariate polynomial equation systems has been the focus of much attention in cryptography in the last years. Since most ciphers can be represented as a system of such equations, the problem of breaking a cipher naturally reduces to the task of solving them. Several papers have appeared on a strategy known as\ eXtended Linearization\ (XL) with a view to assessing its complexity. However, its efficiency seems to have been overestimated and its behaviour has yet to be fully understood. Our aim in this paper is to fill in some of these gaps in our knowledge of XL. In particular, by examining how dependencies arise from multiplication by monomials, we give a formula from which the efficiency of XL can be deduced for multivariate polynomial equations over F_2. \ This confirms rigorously a result arrived at by Yang and Chen by a completely different approach. The formula was verified empirically by investigating huge amounts of random equation systems with varying degree, number of variables and number of equations.},
keywords = {Gr{\"o}bner bases, Stream Ciphers, XL},
isbn = {978-3-540-85911-6},
issn = {0302-9743},
doi = {10.1007/978-3-540-85912-3_22},
url = {http://link.springer.com/chapter/10.1007/978-3-540-85912-3_22},
author = {R{\o}njom, Sondre and Raddum, H{\r a}vard}
}
@article {24082,
title = {Solving Multiple Right Hand Sides linear equations},
journal = {Designs, Codes and Cryptography},
volume = {49},
year = {2008},
month = {04/2008},
pages = {147-160},
publisher = {Springer Verlag},
abstract = {A new method for solving algebraic equation systems common in cryptanalysis is proposed. Our method differs from the others in that the equations are not represented as multivariate polynomials, but as a system of Multiple Right Hand Sides linear equations. The method was tested on scaled versions of the AES. The results overcome significantly what was previously achieved with Gr{\"o}bner Basis related algorithms.},
keywords = {AES, algebraic attacks, Multiple Right Hand Sides linear equations},
doi = {10.1007/s10623-008-9180-z},
url = {http://link.springer.com/article/10.1007/s10623-008-9180-z},
author = {Raddum, H{\r a}vard and Semaev, Igor}
}
@inproceedings {24080,
title = {An Analysis of the Hermes8 Stream Ciphers},
journal = {12th Australasian Conference on Information Security and Privacy, ACISP 2007 },
volume = {4586},
year = {2007},
month = {08/2007},
pages = {1-10},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {Hermes8 [6,7] is one of the stream ciphers submitted to the ECRYPT Stream Cipher Project (eSTREAM [3]). In this paper we present an analysis of the Hermes8 stream ciphers. In particular, we show an attack on the latest version of the cipher (Hermes8F), which requires very few known keystream bytes and recovers the cipher secret key in less than a second on a normal PC. Furthermore, we make some remarks on the cipher{\textquoteright}s key schedule and discuss some properties of ciphers with similar algebraic structure to Hermes8.},
keywords = {Cryptanalysis, Hermes8, Stream Cipher},
isbn = {978-3-540-73457-4},
issn = {0302-9743},
doi = {10.1007/978-3-540-73458-1_1},
url = {http://link.springer.com/chapter/10.1007/978-3-540-73458-1_1},
author = {Babbage, Steve and Cid, Carlos and Pramstaller, Norbert and Raddum, H{\r a}vard}
}
@inproceedings {24081,
title = {MRHS Equation Systems},
journal = {14th International Workshop on Selected Areas in Cryptography, SAC 2007},
volume = {4876},
year = {2007},
month = {08/2007},
pages = {232-245},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {We show how to represent a non-linear equation over\ GF(2) using linear systems with multiple right hand sides. We argue that this representation is particularly useful for constructing equation systems describing ciphers using an S-box as the only means for non-linearity. Several techniques for solving systems of such equations were proposed in earlier work, and are also explained here. Results from experiments with DES are reported. Finally we use our representation to link a particular problem concerning vector spaces to the security of ciphers with S-boxes as the only non-linear operation.},
keywords = {algebraic attacks, Cryptanalysis, DES, non-linear equation systems},
isbn = {978-3-540-77359-7},
issn = {0302-9743},
doi = {10.1007/978-3-540-77360-3_15},
url = {http://link.springer.com/chapter/10.1007/978-3-540-77360-3_15},
author = {Raddum, H{\r a}vard}
}
@inproceedings {24079,
title = {More Dual Rijndaels},
journal = {4th International Conference, AES 2004},
volume = {3373},
year = {2005},
month = {05/2005},
pages = {142-147},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {It is well known that replacing the irreducible polynomial used in the AES one can produce 240 dual ciphers. In this paper we present 9120 other representations of\ GF(28), producing more ciphers dual to the AES. We also show that if the matrix used in the S-box of Rijndael is linear over a larger field than\ GF(2), this would have implications for the XSL attack.},
isbn = {978-3-540-26557-3},
doi = {10.1007/11506447_12},
url = {http://link.springer.com/chapter/10.1007/11506447_12},
author = {Raddum, H{\r a}vard}
}
@article {24077,
title = {On the computation of coset leaders with high Hamming weight},
journal = {Discrete Mathematics},
volume = {274},
year = {2004},
month = {01/2004},
pages = {213-231},
publisher = {Elsevier},
abstract = {The Newton radius of a code is the largest weight of a uniquely correctable error. The covering radius is the largest distance between a vector and the code. In this paper, we use the modular representation of a linear code to give an efficient algorithm for computing coset leaders of relatively high Hamming weight. The weights of these coset leaders serve as lower bounds on the Newton radius and the covering radius for linear codes.},
keywords = {Covering radius, Modular representation, Newton radius},
doi = {10.1016/S0012-365X(03)00090-6},
author = {Raddum, H{\r a}vard}
}
@article {24078,
title = {Weaknesses in the temporal key hash of WPA},
journal = {Mobile Computing and Communications Review},
volume = {8},
year = {2004},
month = {04/2004},
pages = {76-83},
publisher = {ACM Sigmobile},
abstract = {This article describes some weaknesses in the key scheduling in Wi-Fi Protected Access (WPA) put forward to secure the IEEE standard 802.11-1999. Given a few RC4 packet keys in WPA it is possible to find the Temporal Key (TK) and the Message Integrity Check (MIC) key. This is not a practical attack on WPA, but it shows that parts of WPA are weak on their own. Using this attack it is possible to do a TK recovery attack on WPA with complexity\ O(2105) compared to a brute force attack with complexity\ O\ (2128).},
keywords = {802.11, MIC, Michael, temporal key hash, TKIP, WPA},
doi = {10.1145/997122.997132},
author = {Moen, Vebj{\o}rn and Raddum, H{\r a}vard and Kjell J{\o}rgen {Hole}}
}
@inproceedings {24068,
title = {Cryptanalysis of IDEA-X/2},
journal = {Fast Software Encryption},
volume = {2887},
year = {2003},
month = {02/2003},
pages = {1 - 8},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {IDEA is a 64-bit block cipher with a 128-bit key designed by J. Massey and X. Lai. At FSE 2002 a slightly modified version called IDEA-X was attacked using multiplicative differentials. In this paper we present a less modified version of IDEA we call IDEA-X/2, and an attack on this cipher. This attack also works on IDEA-X, and improves on the attack presented at FSE 2002.\ \ },
keywords = {block ciphers, Cryptography, differential cryptanalysis, IDEA},
isbn = {978-3-540-20449-7},
issn = {0302-9743},
doi = {10.1007/978-3-540-39887-5_1},
author = {Raddum, H{\r a}vard}
}
@article {24076,
title = {Distinguishing attack on five-round Feistel networks},
journal = {Electronic Letters},
volume = {39},
year = {2003},
month = {08/2003},
pages = {1175-1177},
publisher = {IEE},
abstract = {Recently it was shown (by J. Patarin) how to distinguish a general five-round Feistel network from a random permutation using O(23n/2) chosen plaintexts or O(27n/4) known plaintexts. The present authors report improvement of these results and a distinguisher is presented which uses roughly 2n\ chosen plaintexts or roughly 23n/2\ known plaintexts.},
doi = {10.1049/el:20030768},
author = {Knudsen, Lars and Raddum, H{\r a}vard}
}
@inproceedings {24063,
title = {A Differential Attack on Reduced-Round SC2000},
journal = {Selected Areas in Cryptography 2001},
volume = {2259},
year = {2001},
month = {12/2001},
pages = {190 - 198},
publisher = {Lecture Notes in Computer Science, Springer Verlag},
abstract = {SC2000 is a 128-bit block cipher with key length of 128, 192 or 256 bits, developed by Fujitsu Laboratories LTD. For 128-bit keys, SC2000 consists of 6.5 rounds, and for 192- and 256-bit keys it consists of 7.5 rounds. In this paper we demonstrate two different 3.5-round differential characteristics that hold with probabilities 2-106\ and 2-107. These characteristics can be used to extract up to 32 bits of the first and last round keys in a 4.5-round variant of SC2000.},
isbn = {978-3-540-43066-7},
issn = {0302-9743},
doi = {10.1007/3-540-45537-X_15},
author = {Raddum, H{\r a}vard and Knudsen, Lars}
}
@inproceedings {24064,
title = {On Noekeon},
journal = {Second Open NESSIE workshop},
year = {2001},
month = {09/2001},
publisher = {Royal Holloway Univerity of London},
address = {London},
abstract = {In this note we analyse Noekeon, a 128-bit block cipher submitted to the NESSIE project. It is shown that for six of seven S-boxes which satisfy the design criteria of the Noekeon designers the resulting block ciphers are vulnerable to either a differential attack, a linear attack or both. One conclusion is that Noekeon is not designed according to the wide trail strategy. Also, it is shown that there exist many related keys for which plaintexts of certain differences result in ciphertexts of certain differences with high probabilities. Noekeon has two key-schedules, one for applications where related-key attacks are not considered dangerous and one for applications where related-key attacks can be mounted. In this paper it is shown that for any given user-selected keys there are many related keys independently of which key-schedule is used.},
author = {Raddum, H{\r a}vard and Knudsen, Lars}
}