kth.sePublications
Change search
Refine search result
123 1 - 50 of 144
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Aknesil, Can
    et al.
    KTH.
    Dubrova, Elena
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    An FPGA Implementation of 4x4 Arbiter PUF2021In: 2021 IEEE 51st international symposium on multiple-valued logic (ISMVL 2021), Institute of Electrical and Electronics Engineers (IEEE) , 2021, p. 160-165Conference paper (Refereed)
    Abstract [en]

    The need of protecting data and bitstreams increases in computation environments such as FPGA as a Service (FaaS). Physically Unclonable Functions (PUFs) have been proposed as a solution to this problem. In this paper, we present an implementation of Arbiter PUF with 4 x 4 switch blocks in Xilinx Series 7 FPGA, perform its statistical analysis, and compare it to other Arbiter PUF variants. We show that the presented implementation utilizes five times less area than 2 x 2 Arbiter PUF-based implementations. It is suitable for many real-world applications, including identification, authentication, key provisioning, and random number generation.

  • 2.
    Aknesil, Can
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    Dubrova, Elena
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    Towards Generic Power/EM Side-Channel Attacks: Memory Leakage on General-Purpose Computers2022In: Proceedings of the 2022 IFIP/IEEE 30th international conference on very large scale integration (VLSI-SOC), Institute of Electrical and Electronics Engineers (IEEE) , 2022Conference paper (Refereed)
    Abstract [en]

    Today's power/EM side-channel analysis is limited by the complexity of the target hardware. We investigate the feasibility of power/EM side-channel analysis of general-purpose computers. This paper makes a step towards this goal by analyzing memory operations of Raspberry Pi 3 Model B, a widely used general-purpose IoT device that is capable of running an operating system, and shows that it is possible to extract information about the data field of memory operations from near-field EM measurements.

  • 3.
    Aknesil, Can
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Dubrova, Elena
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Lindskog, Niklas
    Ericsson AB, Lund, Sweden.
    Englund, Hakan
    Ericsson AB, Lund, Sweden.
    Is your FPGA transmitting secrets: covert antennas from interconnect2023In: 2023 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2023, Institute of Electrical and Electronics Engineers (IEEE) , 2023, p. 79-84Conference paper (Refereed)
    Abstract [en]

    A hidden transmitter embedded into a chip to extract secret information is a well-known type of hardware Trojan. Various ways of implementing covert channels have been proposed in the past. The focus of this paper is covert antennas created from the FPGA interconnect. We present several on-chip antenna implementations that leverage the routing resources of FPGAs. The proposed antennas can transmit data processed by the FPGA with bit-level precision. A near-field probe is used to capture the radiated signal and the transmitted data is restored with 100% accuracy. Our results suggest that introducing a routine screening process for covert antennas in FPGA designs, similar to the one performed for ring oscillators, would be of benefit for FPGA security.

  • 4.
    Backlund, Linus
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Ngo, Kalle
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Gärtner, Joel
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Dubrova, Elena
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Secret Key Recovery Attack on Masked and Shuffled Implementations of CRYSTALS-Kyber and Saber2023In: Applied Cryptography and Network Security Workshops - ACNS 2023 Satellite Workshops, ADSC, AIBlock, AIHWS, AIoTS, CIMSS, Cloud S and P, SCI, SecMT, SiMLA, Proceedings, Springer Nature , 2023, p. 159-177Conference paper (Refereed)
    Abstract [en]

    Shuffling is a well-known countermeasure against side-channel attacks. It typically uses the Fisher-Yates (FY) algorithm to generate a random permutation which is then utilized as the loop iterator to index the processing of the variables inside the loop. The processing order is scrambled as a result, making side-channel attacks more difficult. Recently, a side-channel attack on a masked and shuffled implementation of Saber requiring 61,680 power traces to extract the long-term secret key was reported. In this paper, we present an attack that can recover the long-term secret key of Saber from 4,608 traces. The key idea behind the 13-fold improvement is to recover FY indexes directly, rather than by extracting the message Hamming weight and bit flipping, as in the previous attack. We capture a power trace during the execution of the decryption algorithm for a given ciphertext, recover FY indexes 0 and 255, and extract the corresponding two message bits. Then, we modify the ciphertext to cyclically rotate the message, capture a power trace, and extract the next two message bits with FY indexes 0 and 255. In this way, all message bits can be extracted. By recovering messages contained in k∗ l chosen ciphertexts constructed using a new method based on error-correcting codes of length l, where k is the module rank, we recover the long-term secret key. To demonstrate the generality of the presented approach, we also recover the secret key from a masked and shuffled implementation of CRYSTALS-Kyber, which NIST recently selected as a new public-key encryption and key-establishment algorithm to be standardized.

  • 5.
    Backlund, Linus
    et al.
    KTH.
    Ngo, Kalle
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    Gärtner, Joel
    KTH.
    Dubrova, Elena
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    Secret Key Recovery Attacks on Masked and Shuffled Implementations of CRYSTALS-Kyber and SaberManuscript (preprint) (Other academic)
    Abstract [en]

    Shuffling is a well-known countermeasure against side-channel analysis. It typically uses the Fisher-Yates (FY) algorithm to generate a random permutation which is then utilized as the loop iterator to index the processing of the variables inside the loop. The processing order is scrambled as a result, making side-channel analysis more difficult. Recently, a side-channel attack on a masked and shuffled implementation of Saber requiring 61,680 power traces to extract the secret key was reported. In this paper, we present an attack that can recover the secret key of Saber from 4,608 traces. The key idea behind the 13-fold improvement is to recover FY indexes directly, rather than by extracting the message Hamming weight and bit flipping, as in the previous attack.We capture a power trace during the execution of the decapsulation algorithm for a given ciphertext, recover FY indexes 0 and 255, and extract the corresponding two message bits. Then, we modify the ciphertext to cyclically rotate the message, capture a power trace, and extract the next two message bits with FY indexes 0 and 255. In this way, all message bits can be extracted.By recovering messages contained in $k*l$ chosen ciphertexts constructed using a new method based on error-correcting codes with length $l$, where $k$ is the security level, we recover the long term secret key. To demonstrate the generality of the presented approach, we also recover the secret key from a masked and shuffled implementation of CRYSTALS-Kyber, which NIST recently selected as a new public-key encryption and key-establishment algorithm to be standardized.

    Download full text (pdf)
    fulltext
  • 6.
    Brisfors, Martin
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Forsmark, Sebastian
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Dubrova, Elena
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    How Deep Learning Helps Compromising USIM2021In: Smart Card Research and Advanced Applications, CARDIS 2020 / [ed] Liardet, PY Mentens, N, Springer Nature , 2021, Vol. 12609, p. 135-150Conference paper (Refereed)
    Abstract [en]

    It is known that secret keys can be extracted from some USIM cards using Correlation Power Analysis (CPA). In this paper, we demonstrate a more advanced attack on USIMs, based on deep learning. We show that a Convolutional Neural Network (CNN) trained on one USIM can recover the key from another USIM using at most 20 traces (four traces on average). Previous CPA attacks on USIM cards required high-quality oscilloscopes for power trace acquisition, an order of magnitude more traces from the victim card, and expert-level skills from the attacker. Now the attack can be mounted with a $1000 budget and basic skills in side-channel analysis.

  • 7.
    Brisfors, Martin
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Moraitis, Michail
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    Dubrova, Elena
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    Do Not Rely on Clock Randomization: A Side-Channel Attack on a Protected Hardware Implementation of AES2023In: FPS 2022: Foundations and Practice of Security / [ed] Jourdan, GV Mounier, L Adams, C Sedes, F Garcia-Alfaro, J, Springer Nature , 2023, Vol. 13877, p. 38-53Conference paper (Refereed)
    Abstract [en]

    Clock randomization is one of the oldest countermeasures against side-channel attacks. Various implementations have been presented in the past, along with positive security evaluations. However, in this paper we show that it is possible to break countermeasures based on a randomized clock by sampling side-channel measurements at a frequency much higher than the encryption clock, synchronizing the traces with pre-processing, and targeting the beginning of the encryption. We demonstrate a deep learning-based side-channel attack on a protected FPGA implementation of AES which can recover a subkey from less than 500 power traces. In contrast to previous attacks on FPGA implementations of AES which targeted the last round, the presented attack uses the first round as the attack point. Any randomized clock countermeasure is significantly weakened by an attack on the first round because the effect of randomness accumulated over multiple encryption rounds is lost.

  • 8.
    Chabloz, Jean-Michel
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Sharif Mansouri, Shohreh
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    An Algorithm for Constructing a Fastest Galois NLFSR Generating a Given Sequence2010In: SEQUENCES AND THEIR APPLICATIONS-SETA 2010 / [ed] Carlet C; Pott A, 2010, Vol. 6338, p. 41-54Conference paper (Refereed)
    Abstract [en]

    The problem of efficient implementation of security mechanisms for advanced contactless technologies like RFID is gaining increasing attention. Severe constraints on resources such as area, power consumption, and production cost make the application of traditional cryptographic techniques to these technologies a challenging task. Non-Linear Feedback Shift Register (NLFSR)-based stream ciphers are promising candidates for cryptographic primitives for RFIDs because they have the smallest hardware footprint of all existing cryptographic systems. This paper presents a heuristic algorithm for constructing a fastest Galois NLFSR generating a given sequence. The algorithm takes an NLFSR in the Fibonacci configuration and transforms it to an equivalent Galois NLFSR which has the minimal delay. Our key idea is to find a best position for a given feedback connection without changing the positions of the other feedback connections. We use a technology dependent cost function which approximates the delay of an NLFSR after the technology mapping. The experimental results on 57 NLFSRs used in existing stream ciphers show that, on average, the presented algorithm allows us to decrease the delay by 25.5% as well as to reduce the area by 4.1%.

  • 9.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    A List of Maximum-Period NLFSRs2012Report (Other academic)
    Abstract [en]

    Non-Linear Feedback Shift Registers (NLFSRs) are a generalization of Linear Feedback Shift Registers (LFSRs) in which a current state is a nonlinear function of the previous state. While the theory behind LFSRs is wellunderstood, many fundamental problems related to NLFSRs remain open. Probably the most important one is finding a systematic procedure for constructing NLFSRs with a guaranteed long period. Available algorithms either consider some special cases, or are applicable to small NLFSRs only. In this paper, we present a complete list of n-bit NLFSRs with the period 2n − 1, n < 25, for three different types of feedback functions with algebraic degree two. We hope that the presented experimental data might help analysing feedback functions of maximum-period NLFSRs and finding a supporting theory characterizing them.

    Download full text (pdf)
    fulltext
  • 10.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    A Method for Generating Full Cycles by a Composition of NLFSRs2014In: Designs, Codes and Cryptography, ISSN 0925-1022, E-ISSN 1573-7586, Vol. 73, no 2, p. 469-486Article in journal (Refereed)
    Abstract [en]

    Non-linear feedback shift registers (NLFSRs) are a generalization of linear feedback shift registers in which a current state is a non-linear function of the previous state. The interest in NLFSRs is motivated by their ability to generate pseudo-random sequences which are typically hard to break with existing cryptanalytic methods. However, it is still not known how to construct large -stage NLFSRs which generate full cycles of possible states. This paper presents a method for generating full cycles by a composition of NLFSRs. First, we show that an -stage register with period can be constructed from NLFSRs with -stages by adding to their feedback functions a logic block of size , for . This logic block implements Boolean functions representing pairs of states whose successors have to be exchanged in order to join cycles. Then, we show how to join all cycles into one by using one more logic block of size O(nk).

  • 11.
    Dubrova, Elena
    KTH, Superseded Departments (pre-2005), Electronic Systems Design.
    A polynomial time algorithm for non-disjoint decomposition of multiple-valued functions2004In: 34th International Symposium On Multiple-Valued Logic, Proceedings, 2004, p. 309-314Conference paper (Refereed)
    Abstract [en]

    This paper addresses the problem of non-disjoint decomposition of multiple-valued functions. First, we show that the problem of computing non-disjoint decompositions of a multiple-valued function is related to the problem of finding multiple-vertex dominators of a logic circuit, representing the function. Second, we present an O(n(k)) algorithm for computing all multiple-vertex dominators of a fixed size k, where n is the number of gates of the logic circuit. Our result is important because no polynomial-time algorithm for finding all possible non-disjoint decompositions of multiple-valued functions is known. The presented approach allows us computing a certain subset of non-disjoint decompositions (all reflected in a given circuit structure) in polynomial time. A set of experiments on benchmark circuits illustrates the efficiency of our approach.

  • 12.
    Dubrova, Elena
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    A reconfigurable arbiter PUF with 4 x 4 switch blocks2018In: Proceedings of The International Symposium on Multiple-Valued Logic, IEEE Computer Society , 2018, p. 31-37Conference paper (Refereed)
    Abstract [en]

    Physical Unclonable Functions (PUFs) exploit manufacturing process variation to create responses that are unique to individual integrated circuits (ICs). Typically responses of a PUF cannot be modified once the PUF is fabricated. In applications which use PUFs as a long-Term secret key, it would be useful to have a simple mechanism for reconfiguring the PUF in order to update the key periodically. In this paper, we present a new type of arbiter PUFs which use 4 x 4 switch blocks instead of the conventional 2 x 2 ones. Each 4 x 4 switch block can be reconfigured in many different ways during the PUF's lifetime, making possible regular key updates. 

  • 13.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    A Scalable Method for Constructing Galois NLFSRs With Period 2(n)-1 Using Cross-Join Pairs2013In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 59, no 1, p. 703-709Article in journal (Refereed)
    Abstract [en]

    A method for constructing n-stage Galois NLFSRs with period 2(n) - 1 from n-stage maximum length LFSRs is presented. Nonlinearity is introduced into state cycles by adding a non-linear Boolean function to the feedback polynomial of the LFSR. Each assignment of variables for which this function evaluates to 1 acts as a crossing point for the LFSR state cycle. The effect of non-linearity is cancelled and state cycles are joined back by adding a copy of the same function to a later stage of the register. The presented method requires no extra time steps and it has a smaller area overhead compared to the previous approaches based on cross-join pairs. It is feasible for large n.

  • 14.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    A Transformation From the Fibonacci to the Galois NLFSRs2009In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 55, no 11, p. 5263-5271Article in journal (Refereed)
    Abstract [en]

    Conventional nonlinear feedback shift registers (NLFSRs) use the Fibonacci configuration in which the feedback is applied to the last bit only. In this paper, we show how to transform a Fibonacci NLFSR into an equivalent NLFSR in the Galois configuration, in which the feedback can be applied to every bit. Such a transformation can potentially reduce the depth of the circuits implementing feedback functions, thus decreasing the propagation time and increasing the throughput.

  • 15.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    An equivalence-preserving transformation of shift registers2014In: Sequences and Their Applications - SETA 2014: 8th International Conference, Melbourne, VIC, Australia, November 24-28, 2014, Proceedings, Springer, 2014, p. 187-199Conference paper (Refereed)
    Abstract [en]

    The Fibonacci-to-Galois transformation is useful for reducing the propagation delay of feedback shift register-based stream ciphers and hash functions. In this paper, we extend it to handle Galois-to-Galois case as well as feedforward connections. This makes possible transforming Trivium stream cipher and increasing its keystream data rate by 27% without any penalty in area. The presented transformation might open new possibilities for cryptanalysis of Trivium, since it induces a class of stream ciphers which generate the same set of keystreams as Trivium, but have a different structure.

  • 16.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Bio-Inspired Fault-Tolerance2008In: Proceedings of IEEE/ACM International Conference on Bio-Inspired Models of Network, Information, and Computing Systems (BIONETICS'2008), ICST , 2008Conference paper (Refereed)
    Abstract [en]

    In the last decade, there has been a considerable increase of interest in fault-tolerant computing due to dependability problems related to process scaling, embedded software, and ubiquitous computing. In this paper, we consider an approach to fault-tolerance which is inspired by gene regulatory networks of living cells. Living cells are capable of maintaining their functionality under a variety of genetic changes and external perturbations. They have natural self-healing, self-maintaining, self-replicating and self-assembling mechanisms. The fault-tolerance of living cells is due to the intrinsic robustness of attractors' landscapes of their gene regulatory networks. Previously, we introduced a technique which exploits the stability of attractors to achieve a fault-tolerant computation. In this paper, we evaluate this technique on the example of a gene regulatory network model of Arabidopsis thaliana and show that it can tolerate 70% single-point mutations in the outputs of the defining tables of gene functions.

  • 17.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Fault-tolerant design2013Book (Other academic)
    Abstract [en]

    This textbook serves as an introduction to fault-tolerance, intended for upper-division undergraduate students, graduate-level students and practicing engineers in need of an overview of the field. Readers will develop skills in modeling and evaluating fault-tolerant architectures in terms of reliability, availability and safety. They will gain a thorough understanding of fault tolerant computers, including both the theory of how to design and evaluate them and the practical knowledge of achieving fault-tolerance in electronic, communication and software systems. Coverage includes fault-tolerance techniques through hardware, software, information and time redundancy. The content is designed to be highly accessible, including numerous examples and exercises. Solutions and powerpoint slides are available for instructors.

  • 18.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Finding Matching Initial States for Equivalent NLFSRs in the Fibonacci and the Galois Configurations2010In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 56, no 6, p. 2961-2966Article in journal (Refereed)
    Abstract [en]

    The Fibonacci and the Galois configurations of nonlinear feedback shift registers (NLFSRs) are considered. In the former, the feedback is applied to the input bit of the shift register only. In the latter, the feedback can potentially be applied to every bit. The sufficient conditions for equivalence of NLFSRs in the Fibonacci and the Galois configurations have been formulated previously. The equivalent NLFSRs in different configurations normally have to be initialized to different states to generate the same output sequences. The mapping between the initial states of two equivalent NLFSRs in the Fibonacci and the Galois configurations is derived in this paper.

  • 19.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    How to Speed-Up Your NLFSR-Based Stream Cipher2009In: DATE: 2009 DESIGN, AUTOMATION & TEST IN EUROPE CONFERENCE & EXHIBITION, 2009, p. 878-881Conference paper (Refereed)
    Abstract [en]

    Non-Linear Feedback Shift Registers (NLFSRs) have been proposed as an alternative to Linear Feedback Shift Registers (LFSRs) for generating pseudo-random sequences for stream ciphers. Conventional NLFSRs use the Fibonacci configuration in which the feedback is applied to the last bit only. In this paper, we show how to transform a Fibonacci NLFSR into an equivalent NLFSR in the Galois configuration, in which the feedback can be applied to every bit. Such a transformation can potentially reduce the depth of the circuits implementing feedback functions, thus decreasing the propagation time and increasing the throughput.

  • 20.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Learning Fault-Tolerance from Nature2008In: BEC 2008: 2008 INTERNATIONAL BIENNIAL BALTIC ELECTRONICS CONFERENCE, PROCEEDINGS, 2008, p. 51-58Conference paper (Refereed)
    Abstract [en]

    In the last decade, there has been a considerable increase of interest in fault-tolerant computing due to dependability problems related to process scaling, embedded software, and ubiquitous computing. In this paper, we discuss an approach to fault-tolerance which is inspired by biological systems. Biological systems are capable of maintaining their functionality tinder a variety of genetic changes and external perturbations. They have natural self-healing, self-maintaining, self-replicating and self-assembling mechanisms. We present experimental and numerical evidence that the intrinsic fault-tolerance of biological systems is due to the dynamical phase in which the gene regulatory network operates. The dynamical phase is, in turn, determined by the subtle way in which redundancy is allocated in the network. By understanding the principles of redundancy allocation at the genetic level, we may find ways to build chips that possess the inherent fault-tolerance of biological systems.

  • 21.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Linear-time algorithm for computing minimum checkpoint sets for simulation-based verification of HDL programs2005In: 2005 IEEE International Symposium On Circuits And Systems (ISCAS), Conference Proceedings, IEEE , 2005, p. 2212-2215Conference paper (Refereed)
    Abstract [en]

    Simulation-based verification is a popular method for functional validation of hardware. It is performed by applying a set of tests to the system under consideration and to its reference model, and comparing the results. The effectiveness of a test suite is measured by the fraction of the system covered by the tests. In this paper, we present a technique for selecting a part of the system, called checkpoints, with the property that any set of tests which covers the checkpoints covers the entire system. Thus, by constructing a test suit for the checkpoints, a 100% coverage can be achieved. We present a linear-time algorithm for computing a minimum checkpoint set based on pre- and post-dominator relations of the control flow graph of the HDL program representing the system.

  • 22.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Modeling gene regulatory systems by random Boolean networks2005In: Bioengineered and Bioinspired Systems II / [ed] Carmona, RA; LinanCembrano, G, SPIE - International Society for Optical Engineering, 2005, Vol. 5839, p. 56-65Conference paper (Refereed)
    Abstract [en]

    A random Boolean network is a synchronous Boolean automaton with n vertices. The parameters of an RBN can be tuned so that its statistical features match the characteristics of the gene regulatory system. The number of vertices of the RBN represents the number of genes in tile cell. The number of cycles in the RBN's state space, called attractors, corresponds the number of different cell types. Attractor's length corresponds to the cell cycle time. Sensitivity of the attractors to different kind of perturbations, modeled by changing the state of a particular vertex, associated Boolean function, or network edge, reflects the stability of the cell to damage, mutations and virus attacks. In order to evaluate the attractors, their number and length have to be re-computed repeatedly. For large RBN's, searching for attractors in the O(2(n)) state space is an infeasible task. Fortunately, only a subset of vertices of an RBN, called relevant vertices, determines its dynamics. The remaining vertices are redundant. In this paper, we present an algorithm for identifying redundant vertices in RBNs which allows us to reduce the search space for computing at.tractors from O(2(n)) to Theta(2 root n). We also show how RBNs can be used for studying evolution.

  • 23.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Multiple-Valued Logic in VLSI: Challenges and Opportunities1999In: Proceedings of NORCHIP'99, IEEE conference proceedings, 1999Conference paper (Refereed)
  • 24.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Multiple-Valued Logic Synthesis and Optimization2002In: Logic Synthesis and Verification / [ed] S. Hassoun and T. Sasao, Springer, 2002, 1st, p. 89-114Chapter in book (Refereed)
  • 25.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    On Constructing Secure and Hardware-Efficient Invertible Mappings2016In: Proceedings of IEEE International Symposium on Multiple-Valued Logic, IEEE Computer Society, 2016Conference paper (Refereed)
    Abstract [en]

    Our society becomes increasingly dependent on wireless communications. The tremendous growth in the number and type of wirelessly connected devices in a combination with the dropping cost for performing cyberattacks create new challenges for assuring security of services and applications provided by the next generation of wireless communication networks. The situation is complicated even further by the fact that many end-point Internet of Things (IoT) devices have very limited resources for implementing security functionality. This paper addresses one of the aspects of this important, many-faceted problem - the design of hardware-efficient cryptographic primitives suitable for the protection of resource-constrained IoT devices. We focus on cryptographic primitives based on the invertible mappings of type {0,1,…,2n−1}→{0,1,…,2n−1}. In order to check if a given mapping is invertible or not, we generally need an exponential in n number of steps. In this paper, we derive a sufficient condition for invertibility which can be checked in O(n2N) time, where N is the size of representation of the largest function in the mapping. Our results can be used for constructing cryptographically secure invertible mappings which can be efficiently implemented in hardware.

  • 26.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Phylogenetic networks with edge-disjoint recombination cycles2005In: Bioengineered and Bioinspired Systems II / [ed] Carmona, RA; LinanCembrano, G, SPIE - International Society for Optical Engineering, 2005, Vol. 5839, p. 381-388Conference paper (Refereed)
    Abstract [en]

    Phylogenetic analysis is a branch of biology that establishes the evolutionary relationships between living organisms. The goal of phylogenetic analysis is to determine the order and approximate timing of speciation events in the evolution of a given set of species. Phylogenetic networks allow to represent evolutionary histories that include events like recombination and hybridization. In this paper, we introduce a class of phylogenetic networks called extended galled-trees in which recombination cycles share no edge. We show that the site consistency problem, which is NP-hard in general, can be solved in polynomial time for this class of phylogenetic networks.

  • 27.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Random Multiple-Valued Networks: Theory and Applications2006In: Proceedings of The International Symposium on Multiple-Valued Logic, New York: IEEE , 2006, p. 159-164Conference paper (Refereed)
    Abstract [en]

    A living cell is essentially a molecular digital computer that configures itself as part of the execution of its code. By understanding how cells direct the assembly, of their Molecules, we can find ways to build computer Chips that can self-organize, evolve and adapt to a changing environment, In this paper we consider a model of the gene regulatory, network of living cells called random multiple-valued network (RMN). An RMN can be tuned so that its statistical features match the characteristics of living cells. We present a set of algorithms for redundancy removal, partitioning and computation of attractors in RMNs. We also discuss how RMNs can be used for implementing logic functions.

  • 28.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Self-Organization for Fault-Tolerance2008In: SELF-ORGANIZING SYSTEMS, PROCEEDINGS / [ed] Hummel KA; Sterbenz JPG, 2008, Vol. 5343, p. 145-156Conference paper (Refereed)
    Abstract [en]

    In the last decade, there has been a considerable increase of interest in fault-tolerant computing due to dependability problems related to process scaling, embedded systems, and ubiquitous Computing, In this paper, we present an approach to fault-tolerance inspired by gene regulatory networks of living cells. Living cells are capable of maintaining their functionality under a variety of genetic changes and external perturbations. They have natural self-healing, self-maintaining, self-replicating, and self-assembling mechanisms. The fault-tolerance of living cells is due to the ability of their gene regulatory network to self-organize and produce a stable attractors' landscape. We introduce a computational scheme which exploits the intrinsic stability of attractors to achieve fault.-tolerant computation. We also test fault-tolerance of the presented scheme on the example of a gene regulatory network model of Arabidopsis thaliana and show that it can tolerate 68% single-point mutations in the outputs of the defining tables of gene functions.

  • 29.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Structural testing based on minimum kernels2005In: Proceedings -Design, Automation and Test in Europe, DATE '05 / [ed] Wehn, N; Benini, L, IEEE Computer Society, 2005, p. 1168-1173Conference paper (Refereed)
    Abstract [en]

    Structural testing techniques, such as statement and branch coverage, play an important role in improving dependability of software systems. However, finding a set of tests which guarantees high coverage is a time-consuming task. In this paper we present a technique for structural testing based on kernel computation. A kernel satisfies the property that any set of tests which executes all vertices (edges) of the kernel executes all vertices (edges) of the program's flowgraph. We present a linear-time algorithm for computing minimum kernels based on pre- and post-dominator relations of a flowgraph.

  • 30.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Synthesis of Binary Machines2011In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 57, no 10, p. 6890-6893Article in journal (Refereed)
    Abstract [en]

    The problem of constructing a binary machine with the minimum number of stages generating a given binary sequence is addressed. Binary machines are a generalization of nonlinear feedback shift registers (NLFSRs) in which both connections, feedback and feedforward, are allowed and no chain connection between the register stages is required. An algorithm for constructing a shortest binary machine generating a given periodic binary sequence is presented.

  • 31.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Synthesis of NLFSR-based pseudo-random sequence generators for stream ciphers2008In: Proceedings of International Symposium on Applied Computing (IADIS’2008), 2008Conference paper (Refereed)
  • 32.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Synthesis of parallel binary machines2011In: Computer-Aided Design (ICCAD), 2011 IEEE/ACM International Conference on, 2011, p. 200-206Conference paper (Refereed)
    Abstract [en]

    Binary machines are a generalization of Feedback Shift Registers (FSRs) in which both, feedback and feedforward, connections are allowed and no chain connection between the register stages is required. In this paper, we present an algorithm for synthesis of binary machines with the minimum number of stages for a given degree of parallelization. Our experimental results show that for sequences with high linear complexity such as complementary, Legendre, or truly random, parallel binary machines are an order of magnitude smaller than parallel FSRs generating the same sequence. The presented approach can potentially be of advantage for many applications including wireless communication, cryptography, and testing.

  • 33.
    Dubrova, Elena
    et al.
    KTH, Superseded Departments (pre-2005), Electronic Systems Design.
    Ellervee, P.
    Miller, D. M.
    Muzio, J. C.
    Sullivan, A. J.
    TOP: an algorithm for three-level combinational logic optimisation2004In: IEE Proceedings - Circuits Devices and Systems, ISSN 1350-2409, E-ISSN 1359-7000, Vol. 151, no 4, p. 307-314Article in journal (Refereed)
    Abstract [en]

    Three-level logic is shown to have a potential for reducing the area over two-level implementations, as well as for a gain in speed over multilevel implementations. A heuristic algorithm TOP is presented, targeting a three-level logic expression of type g(1degrees)g(2), where g(1) and g(2) are sum-of-products expressions and '(degrees)' is a binary operation. For the first time, to the authors' knowledge, this problem is addressed for an arbitrary operation '(degrees)', although several algorithms for specified cases of '(degrees)' have been presented in the past. The experimental results show that, on average, the total number of product-terms in the expression obtained by TOP is about one third of the number of product-terms in the expression obtained by a two-level AND-OR minimiser.

  • 34.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Hell, Martin
    Lund University, Sweden.
    Espresso: A stream cipher for 5G wireless communication systems2017In: Cryptography and Communications, ISSN 1936-2447, E-ISSN 1936-2455, Vol. 9, no 2, p. 273-289Article in journal (Refereed)
    Abstract [en]

    The demand for more efficient ciphers is a likely to sharpen with new generation of products and applications. Previous cipher designs typically focused on optimizing only one of the two parameters - hardware size or speed, for a given security level. In this paper, we present a methodology for designing a class of stream ciphers which takes into account both parameters simultaneously. We combine the advantage of the Galois configuration of NLFSRs, short propagation delay, with the advantage of the Fibonacci configuration of NLFSRs, which can be analyzed formally. According to our analysis, the presented stream cipher Espresso is the fastest among the ciphers below 1500 GE, including Grain-128 and Trivium.

  • 35.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Liu, Ming
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Teslenko, Maxim
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Finding Attractors in Synchronous Multiple-Valued Networks Using SAT-based Bounded Model Checking2012In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 19, no 1-3, p. 109-131Article in journal (Refereed)
    Abstract [en]

    Synchronous multiple-valued networks are a discrete-space discrete-time model of the gene regulatory network of living cells. In this model, cell types are represented by the cycles in the state transition graph of a network, called attractors. When the effect of a disease or a mutation on a cell is studied, attractors have to be re-computed each time a fault is injected in the model. This motivates research on algorithms for finding attractors. Existing decision diagram-based approaches have limited capacity due to the excessive memory requirements of decision diagrams. Simulation-based approaches can be applied to larger networks, however, they are incomplete. We present an algorithm for finding attractors which uses a SAT-based bounded model checking. Our model checking approach exploits the deterministic nature of the network model to reduce runtime. Although the idea of applying model checking to the analysis of gene regulatory networks is not new, to our best knowledge, we are the first to use it for computing all attractors in a model. The efficiency of the presented algorithm is evaluated by analyzing 7 networks models of real biological processes as well as 35.000 randomly generated 4-valued networks. The results show that our approach has a potential to handle an order of magnitude larger models than currently possible.

  • 36.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Mansouri, Shohreh
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    A BDD-Based Method for LFSR Parellelization with Application to Fast CRC Encoding2013In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 21, no 5, p. 561-575Article in journal (Refereed)
    Abstract [en]

    Galois Fields of order $2^k$, $GF(2^k)$, provide a unified theoretical framework for constructing parallel devices generating $k$ output bits per clock cycle. In this paper, we use $GF(2^k)$ for constructing Linear Feedback Shift Registers (LFSRs) for the parallel encoding of Cyclic Redundancy Check (CRC) codes.CRC codes are widely used in data communication and storage for detecting burst errors. Traditional methods for the parallel encoding of CRC are based on computing the $k$th power of the connection matrix of the LFSR. We propose an alternative method based on computing the $k$th power of the transition relation of the LFSR. We use Binary Decision Diagrams (BDDs) for representing the transition relation in a partitioned form. This allows us to bound the size of BDDs by $O(n^2)$, where $n$ is the size of the LFSR. The presented algorithm is asymptotically faster than previous algorithms for LFSR parallelization.

  • 37.
    Dubrova, Elena
    et al.
    KTH, Superseded Departments (pre-2005), Microelectronics and Information Technology, IMIT.
    Muzio, J. C.
    Easily testable multiple-valued logic circuits derived from Reed-Muller circuits2000In: IEEE Transactions on Computers, ISSN 0018-9340, E-ISSN 1557-9956, Vol. 49, no 11, p. 1285-1289Article in journal (Refereed)
    Abstract [en]

    In 1972, Reddy showed that the binary circuits realizing Reed-Muller canonical form are easily testable. In this paper, we extend Reddy's result to multiple-valued logic circuits. employing more than two discrete levels of signal, The electronic fabrication of such circuits became feasible due to the recent advances in integrated circuit technology. We show that, in the multiple-valued case, several new phenomena occur which allow us to asymptotically reduce the upper bound on the number of tests required for fault detection, but make the generation of tests harder.

  • 38.
    Dubrova, Elena
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Naslund, Mats
    Ericsson AB, Ericsson Res, Stockholm, Sweden..
    Selander, Göran
    Ericsson AB, Ericsson Res, Stockholm, Sweden..
    Lindqvist, Fredrik
    Ericsson AB, Ericsson Res, Stockholm, Sweden..
    Message authentication based on cryptographically secure CRC without polynomial irreducibility test2018In: Cryptography and Communications, ISSN 1936-2447, E-ISSN 1936-2455, Vol. 10, no 2, p. 383-399Article in journal (Refereed)
    Abstract [en]

    In this paper, we present a message authentication scheme based on cryptographically secure cyclic redundancy check (CRC). Similarly to previously proposed cryptographically secure CRCs, the presented one detects both random and malicious errors without increasing bandwidth. The main difference from previous approaches is that we use random instead of irreducible generator polynomials. This eliminates the need for irreducibility tests. We provide a detailed quantitative analysis of the achieved security as a function of message and CRC sizes. The results show that the presented scheme is particularly suitable for the authentication of short messages.

  • 39.
    Dubrova, Elena
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    Ngo, Kalle
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    Gärtner, Joel
    KTH.
    Breaking a Fifth-Order Masked Implementation of CRYSTALS-Kyber by Copy-PasteManuscript (preprint) (Other academic)
    Abstract [en]

    CRYSTALS-Kyber has been selected by the NIST as a public-key encryption and key encapsulation mechanism to be standardized. It is also included in the NSA's suite of cryptographic algorithms recommended for national security systems. This makes it  important to evaluate the resistance of CRYSTALS-Kyber's implementations to side-channel attacks. The unprotected and first-order masked software implementations have been already analysed. In this paper, we present deep learning-based message recovery attacks on the $\omega$-order masked implementations of CRYSTALS-Kyber in ARM Cortex-M4 CPU for $\omega \leq 5$. The main contribution is a new neural network training method called {\em recursive learning}. In the attack on an $\omega$-order masked implementation, we start training from an artificially constructed neural network $M^{\omega}$ whose weights are partly copied from a model $M^{\omega-1}$ trained on the $(\omega-1)$-order masked implementation, and then extended to one more share. Such a method allows us to train neural networks that can recover a message bit with the probability above 99\% from high-order masked implementations. 

    Download full text (pdf)
    fulltext
  • 40.
    Dubrova, Elena
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    Ngo, Kalle
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    Gärtner, Joel
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    Wang, Ruize
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Breaking a Fifth-Order Masked Implementation of CRYSTALS-Kyber by Copy-Paste2023In: PROCEEDINGS OF THE 10TH ACM ASIA PUBLIC-KEY CRYPTOGRAPHY WORKSHOP, APKC 2023, Association for Computing Machinery (ACM) , 2023, p. 10-20Conference paper (Refereed)
    Abstract [en]

    CRYSTALS-Kyber has been selected by the NIST as a public-key encryption and key encapsulation mechanism to be standardized. It is also included in the NSA's suite of cryptographic algorithms recommended for national security systems. This makes it important to evaluate the resistance of CRYSTALS-Kyber's implementations to side-channel attacks. The unprotected and first-order masked software implementations have been already analysed. In this paper, we present deep learning-based message recovery attacks on the omega-order masked implementations of CRYSTALS-Kyber in ARM Cortex-M4 CPU for omega <= 5. The main contribution is a new neural network training method called recursive learning. In the attack on an omega-order masked implementation, we start training from an artificially constructed neural network M-omega whose weights are partly copied from a model M omega-1 trained on the (omega - 1)-order masked implementation, and then extended to one more share. Such a method allows us to train neural networks that can recover a message bit with the probability above 99% from high-order masked implementations.

  • 41.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Näslund, Mats
    Ericsson AB.
    Carlsson, Gunnar
    Ericsson AB.
    Fornehed, John
    Ericsson AB.
    Smeets, Ben
    Ericsson AB.
    Two Countermeasures Against Hardware Trojans Exploiting Non-Zero Aliasing Probability of BIST2016In: Journal of Signal Processing Systems, ISSN 1939-8018, E-ISSN 1939-8115Article in journal (Refereed)
    Abstract [en]

    The threat of hardware Trojans has been widely recognized by academia, industry, and government agencies. A Trojan can compromise security of a system in spite of cryptographic protection. The damage caused by a Trojan may not be limited to a business or reputation, but could have a severe impact on public safety, national economy, or national security. An extremely stealthy way of implementing hardware Trojans has been presented by Becker et al. at CHES’2012. Their work have shown that it is possible to inject a Trojan in a random number generator compliant with FIPS 140-2 and NIST SP800-90 standards by exploiting non-zero aliasing probability of Logic Built-In-Self-Test (LBIST). In this paper, we present two methods for modifying LBIST to prevent such an attack. The first method makes test patterns dependent on a configurable key which is programed into a chip after the manufacturing stage. The second method uses a remote test management system which can execute LBIST using a different set of test patterns at each test cycle.

  • 42.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Näslund, Mats
    Ericsson, Sweden.
    Carlsson, Gunnar
    Ericsson, Sweden.
    Smeets, Ben
    Ericsson, Sweden.
    Keyed Logic BIST for Trojan Detection in SoC2014In: Proceedings of IEEE International Symposium on System-on-Chip (SOC'2014), IEEE conference proceedings, 2014Conference paper (Refereed)
    Abstract [en]

    As demonstrated by the recent attack on Intel’s Ivy Bridge processor, the traditional Logic Built-In Self-Test (LBIST) methods do not provide adequate protection of SoC against malicious modifications known as hardware Trojans. In this paper, we introduce a simple but efficient countermeasure against hardware Trojans which exploits non-zero aliasing probability of LBIST. We propose to generate LBIST test patterns based on a configurable key which is decided and programed into the circuit after the manufacturing stage. Since the key and hence expected LBIST signature are unknown at the manufacturing stage, an attack based on selecting suitable values for the Trojan which result in the same signature as a fault-free circuit signature becomes infeasible.

  • 43.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Näslund, Mats
    Ericsson AB.
    Selander, Göran
    Ericsson AB.
    CRC-Based Message Authentication for 5G Mobile Technology2015In: Proceedings of 2015 IEEE Trustcom/BigDataSE/ISPA, Institute of Electrical and Electronics Engineers (IEEE), 2015, Vol. 1, p. 1186-1191Conference paper (Refereed)
    Abstract [en]

    Our society greatly depends on mobile technologies. As wirelessly connected devices take over the control of the electricity in our homes, the water we drink and the transportation we use, it becomes increasingly important to guarantee the security of interactions of all players involved in a network. Apart from the high security needs, 5G will require utmost efficiency in the use of bandwidth and energy. In this paper, we show how to make the type of CRC checksum used in current LTE standards cryptographically secure with minimum extra resources. We present a new CRC-based message authentication method and provide a quantitative analysis of the achieved security as a function of message and CRC sizes. The presented method retains most of the implementation simplicity of the traditional CRC except that the LFSR implementing the encoding and decoding is required to have re-programmable connections. Similarly to previously proposed cryptographically secure CRCs, the presented CRC enables combining the detection of random and malicious errors without increasing bandwidth. Its main advantage is the ability to detect all double-bit errors in a message, which is of special importance for systems using Turbo codes, including LTE.

  • 44.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Näslund, Mats
    Ericsson Research, Sweden .
    Selander, Göran
    Ericsson Research, Sweden .
    Secure and Efficient LBIST for Feedback Shift Register-Based Cryptographic Systems2014In: Proceedings of 19th IEEE European Test Symposium (ETS'2014), IEEE conference proceedings, 2014Conference paper (Refereed)
    Abstract [en]

    Cryptographic methods are used to protect confidential information against unauthorised modification or disclo-sure. Cryptographic algorithms providing high assurance exist, e.g. AES. However, many open problems related to assuring security of a hardware implementation of a cryptographic algorithm remain. Security of a hardware implementation can be compromised by a random fault or a deliberate attack. The traditional testing methods are good at detecting random faults, but they do not provide adequate protection against malicious alterations of a circuit known as hardware Trojans. For example, a recent attack on Intel's Ivy Bridge processor demonstrated that the traditional Logic Built-In Self-Test (LBIST) may fail even the simple case of stuck-at fault type of Trojans. In this paper, we present a novel LBIST method for Feedback Shift Register (FSR)-based cryptographic systems which can detect such Trojans. The specific properties of FSR-based cryptographic systems allow us to reach 100% single stuck-at fault coverage with a small set of deterministic tests. The test execution time of the proposed method is at least two orders of magnitude shorter than the one of the pseudo-random pattern-based LBIST. Our results enable an efficient protection of FSR-based cryptographic systems from random and malicious stuck-at faults.

  • 45.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Näslund, Mats
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Selander, Göran
    Tsiatsis, Vlasios
    Energy-Efficient Message Authentication for IEEE 802.15.4-Based Wireless Sensor Networks2014In: Proceedings of 32nd Nordic Microelectronics Conference NORCHIP , IEEE conference proceedings, 2014Conference paper (Refereed)
    Abstract [en]

    The number of wirelessly connected devices is expected to increase to a few tens of billions by the year 2020. Newer generations of products and applications will sharpen demands for ultra-low energy consuming wireless devices. Various techniques for energy saving based on Discontinuous Reception (DRX) are known. However, DRX is vulnerable to unauthorized or fake trigger requests by malicious adversaries aiming to drain a device's battery. Existing message authentication methods can identify spoofed messages, but they require the reception of a complete message before its authenticity can be verified. In this paper, we present a method which inserts authentication checkpoints at several positions within a message. This enables a device to identify that a message is unauthorized and turn its radio receiver off as soon as the first checkpoint fails. The presented method has a low complexity with respect to the computational and memory resources and does not slow down the receiver. It can maintain the packet format prescribed by the IEEE 802.15.4 specification, which provides for backward compatibility. Finally, it incorporates authentication checkpoints at the MAC layer, which allows nodes that do not employ the presented method to participate in the communication.

  • 46.
    Dubrova, Elena
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Näslund, Oskar
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Degen, Bernhard
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Gawell, Anders
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    Yu, Yang
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems.
    CRC-PUF: A Machine Learning Attack Resistant Lightweight PUF Construction2019In: 2019 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW), IEEE conference proceedings, 2019, p. 264-271Conference paper (Refereed)
    Abstract [en]

    Adversarial machine learning is an emerging threat to security of Machine Learning (ML)-based systems. However, we can potentially use it as a weapon against ML-based attacks. In this paper, we focus on protecting Physical Unclonable Functions (PUFs) against ML-based modeling attacks. PUFs are an important cryptographic primitive for secret key generation and challenge-response authentication. However, none of the existing PUF constructions are both ML attack resistant and sufficiently lightweight to fit low-end embedded devices. We present a lightweight PUF construction, CRC-PUF, in which input challenges are de-synchronized from output responses to make a PUF model difficult to learn. The de-synchronization is done by an input transformation based on a Cyclic Redundancy Check (CRC). By changing the CRC generator polynomial for each new response, we assure that success probability of recovering the transformed

    Download full text (pdf)
    fulltext
  • 47.
    Dubrova, Elena
    et al.
    KTH, Superseded Departments (pre-2005), Electronic Systems Design.
    Sack, H.
    Probabilistic equivalence checking of multiple-valued functions2004In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 10, no 4, p. 395-414Article in journal (Refereed)
    Abstract [en]

    This paper describes a probabilistic method for verifying the equivalence of two multiple-valued functions. Each function is hashed to an integer code by transforming it to a integer-valued polynomial and evaluating it for values of variables taken independently and uniformly at random from a finite field. Since the polynomial is unique for a given function, if two hash codes are different, then the functions are not equivalent. However, if two hash codes are the same, the functions may or may not be equivalent, because different polynomials may happen to hash to the same code. Thus, the method presented in this paper determines the equivalence of two functions with a known (small) probability of error, arising from collisions between inequivalent functions. Such a method seems to be an attractive alternative for verifying functions that are too large to be handled by deterministic equivalence checking methods.

  • 48.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Sarif Mansouri, Shohreh
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    A BDD-based approach to constructing LFSRs for parallel CRC encoding2012In: Proceedings, IEEE 42nd International Symposium on Multiple-Valued Logic. ISMVL 2012, IEEE Computer Society, 2012, p. 128-133Conference paper (Refereed)
    Abstract [en]

    Cyclic Redundancy Check codes (CRC) are widely used in data communication and storage devices for detecting burst errors. In applications requiring high-speed data transmission, multiple bits of an CRC are computed in parallel. Traditional methods for constructing an Linear Feedback Shift Register (LFSR) generating k bits of an CRC in parallel are based on computing kth power of the connection matrix of the LFSR. We propose an alternative method which is based on computing kth power of the transition relation of the LFSR. We use Binary Decision Diagrams (BDDs) for representing the transition relation and we keep the transition relation partitioned. This allows us to bound the size of BDDs by O(n(2)), where n is the size of the LFSR. Our experimental results show that the presented algorithm asymptotically improves the complexity of previous approaches.

  • 49.
    Dubrova, Elena
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electronics and Embedded systems, Electronic and embedded systems.
    Selander, G.
    Näslund, Mats
    KTH.
    Lindqvist, Fredrik
    KTH.
    Lightweight message authentication for constrained devices2018In: WiSec 2018 - Proceedings of the 11th ACM Conference on Security and Privacy in Wireless and Mobile Networks, Association for Computing Machinery (ACM), 2018, p. 196-201Conference paper (Refereed)
    Abstract [en]

    Message Authentication Codes (MACs) used in today's wireless communication standards may not be able to satisfy resource limitations of simpler 5G radio types and use cases such as machine type communications. As a possible solution, we present a lightweight message authentication scheme based on the cyclic redundancy check (CRC). It has been previously shown that a CRC with an irreducible generator polynomial as the key is an -almost XOR-universal (AXU) hash function with = (m + n)/2n-1, where m is the message size and n is the CRC size. While the computation of n-bit CRCs can be efficiently implemented in hardware using linear feedback shift registers, generating random degree-n irreducible polynomials is computationally expensive for large n. We propose using a product of k irreducible polynomials whose degrees sum up to n as a generator polynomial for an n-bit CRC and show that the resulting hash functions are -AXU with = (m + n)k/2n -k. The presented message authentication scheme can be seen as providing a trade-off between security and implementation efficiency.

  • 50.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Sharif Mansouri, Shohreh
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    A BDD-Based Method for LFSR Parallelization with Application to Fast CRC Encoding2013In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 21, no 5-6, p. 561-574Article in journal (Refereed)
    Abstract [en]

    Galois Fields of order 2(k), GF(2(k)), provide a unified theoretical framework for constructing parallel devices generating k output bits per clock cycle. In this paper, we use GF(2(k)) for constructing Linear Feedback Shift Registers (LFSRs) for the parallel encoding of Cyclic Redundancy Check (CRC) codes. CRC codes are widely used in data communication and storage for detecting burst errors. Traditional methods for the parallel encoding of CRC are based on computing the kth power of the connection matrix of the LFSR. We propose an alternative method based on computing the kth power of the transition relation of the LFSR. We use Binary Decision Diagrams (BDDs) for representing the transition relation in a partitioned form. This allows us to bound the size of BDDs by O(n(2)), where it is the size of the LFSR. The presented algorithm is asymptotically faster than previous algorithms for LFSR parallelization.

123 1 - 50 of 144
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf