1-10hit |
Hideo FUJIWARA Katsuya FUJIWARA Toshinori HOSOKAWA
Linear feed-forward/feedback shift registers are used as an effective tool of testing circuits in various fields including built-in self-test and secure scan design. In this paper, we consider the issue of testing linear feed-forward/feedback shift registers themselves. To test linear feed-forward/feedback shift registers, it is necessary to generate a test sequence for each register. We first present an experimental result such that a commercial ATPG (automatic test pattern generator) cannot always generate a test sequence with high fault coverage even for 64-stage linear feed-forward/feedback shift registers. We then show that there exists a universal test sequence with 100% of fault coverage for the class of linear feed-forward/feedback shift registers so that no test generation is required, i.e., the cost of test generation is zero. We prove the existence theorem of universal test sequences for the class of linear feed-forward/feedback shift registers.
Hiroshi NOMAGUCHI Chunhua SU Atsuko MIYAJI
RFID enable applications are ubiquitous in our society, especially become more and more important as IoT management rises. Meanwhile, the concern of security and privacy of RFID is also increasing. The pseudorandom number generator is one of the core primitives to implement RFID security. Therefore, it is necessary to design and implement a secure and robust pseudo-random number generator (PRNG) for current RFID tag. In this paper, we study the security of light-weight PRNGs for EPC Gen2 RFID tag which is an EPC Global standard. For this reason, we have analyzed and improved the existing research at IEEE TrustCom 2017 and proposed a model using external random numbers. However, because the previous model uses external random numbers, the speed has a problem depending on the generation speed of external random numbers. In order to solve this problem, we developed a pseudorandom number generator that does not use external random numbers. This model consists of LFSR, NLFSR and SLFSR. Safety is achieved by using nonlinear processing such as multiplication and logical multiplication on the Galois field. The cycle achieves a cycle longer than the key length by effectively combining a plurality of LFSR and the like. We show that our proposal PRNG has good randomness and passed the NIST randomness test. We also shows that it is resistant to identification attacks and GD attacks.
Dynamic linear feedback shift registers (DLFSRs) are a scheme to transfer from one LFSR to another. In cryptography each LFSR included in a DLFSR should generate maximal-length sequences, and the number of switches transferring LFSRs should be small for efficient performance. This corresponding addresses on searching such conditioned DLFSRs. An efficient probabilistic algorithm is given to find such DLFSRs with two or four switches, and it is proved to succeed with nonnegligible probability.
Pao-Lung CHEN Da-Chen LEE Wei-Chia LI
This work presents a novel counter-based randomization method for use in a flying-adder frequency synthesizer with a cost-effective structure that can replace the fractional accumulator. The proposed technique involves a counter, a comparator and a modified linear feedback shift register. The power consumption and speed bottleneck of the conventional flying-adder are significantly reduced. The modified linear shift feedback register is used as a pseudo random data generator, suppressing the spurious tones arise from the periodic carry sequences that is generated by the fractional accumulator. Furthermore, the proposed counter-based randomization method greatly reduces the large memory size that is required by the conventional approach to carry randomization. A test chip for the proposed counter-based randomization method is fabricated in the TSMC 0.18,$mu $m 1P6M CMOS process, with the core area of 0.093,mm$^{mathrm{2}}$. The output frequency had a range of 43.4,MHz, extasciitilde 225.8,MHz at 1.8,V with peak-to-peak jitter (Pk-Pk) jitter 139.2,ps at 225.8,MHz. Power consumption is 2.8,mW @ 225.8,MHz with 1.8 supply voltage.
Zhongxiao WANG Wenfeng QI Huajin CHEN
Recently nonlinear feedback shift registers (NFSRs) have frequently been used as basic building blocks for stream ciphers. A major problem concerning NFSRs is to construct NFSRs which generate de Bruijn sequences, namely maximum period sequences. In this paper, we present a new necessary condition for NFSRs to generate de Bruijn sequences. The new condition can not be deduced from the previously proposed necessary conditions. It is shown that the number of NFSRs whose feedback functions satisfy all the previous necessary conditions but not the new one is very large.
Çağdaş ÇALIK Meltem SÖNMEZ TURAN Ferruh ÖZBUDAK
Feedback shift registers are basic building blocks for many cryptographic primitives. Due to the insecurities of Linear Feedback Shift Register (LFSR) based systems, the use of Nonlinear Feedback Shift Registers (NFSRs) became more popular. In this work, we study the feedback functions of NFSRs with period 2n. First, we provide two new necessary conditions for feedback functions to be maximum length. Then, we consider NFSRs with k-monomial feedback functions and focus on two extreme cases where k=4 and k=2n-1. We study construction methods for these special cases.
Akio TSUNEDA Kunihiko KUDO Daisaburo YOSHIOKA Takahiro INOUE
We propose feedback-limited NFSRs (nonlinear feedback shift registers) which can generate periodic sequences of period 2k-1, where k is the length of the register. We investigate some characteristics of such periodic sequences. It is also shown that the scale of such NFSRs can be reduced by the feedback limitation. Some simulation and experimental results are shown including comparison with LFSRs (linear feedback shift registers) for conventional M-sequences and Gold sequences.
Miodrag J. MIHALJEVIC Hideki IMAI
It is shown that the effective secret-key size of TOYOCRYPT-HS1 stream cipher is only 96 bits, although the secret key consists of 128 bits. This characteristic opens a door for developing an algorithm for cryptanalysis based on the time-memory-data trade-off with the overall complexity significantly smaller than the exhaustive search over the effective key space.
Miodrag J. MIHALJEVIC Marc P. C. FOSSORIER Hideki IMAI
An algorithm for cryptanalysis of certain keystream generators is proposed. The developed algorithm has the following two advantages over other reported ones: it is more powerful, and it can be implemented by a high-speed software or a simple hardware suitable for high parallel architectures. The algorithm is based on error-correction of information bits only (of the corresponding binary block code) with a novel method for construction of the parity-checks, and the employed error-correction procedure is an APP based threshold decoding. Experimental and theoretical analyses of the algorithm performance are presented, and its complexity is evaluated. The proposed algorithm is compared with recently proposed improved fast correlation attacks based on convolutional codes and turbo decoding. The underlying principles, performance and complexity are compared, and the gain obtained with the novel approach is pointed out.
Tomoko K. MATSUSHIMA Toshiyasu MATSUSHIMA Shigeichi HIRASAWA
This paper presents a new architecture for multiple-input signature analyzers. The proposed signature analyzer with Hδ inputs is designed by parallelizing a GLFSR(δ,m), where δ is the number of input signals and m is the number of stages in the feedback shift register. The GLFSR, developed by Pradhan and Gupta, is a general framework for representing LFSR-based signature analyzers. The parallelization technique described in this paper can be applied to any kind of GLFSR signature analyzer, e. g. , SISRs, MISRs, multiple MISRs and MLFSRs. It is shown that a proposed signature analyzer with Hδ inputs requires less complex hardware than either single GLFSR(Hδ,m)s or a parallel construction of the H original GLFSR(δ,m)s. It is also shown that the proposed signature analyzer, while requiring simpler hardware, has comparable aliasing probability with analyzers using conventional GLFSRs for some CUT error models of the same test response length and test time. The proposed technique would be practical for testing CUTs with a large number of output sequences, since the test circuit occupies a smaller area on the LSI chip than the conventional multiple-input signature analyzers of comparable aliasing probability.