The RSA cryptosystem, named after its inventors, Rivest, Shamir and Adleman, is the most widely known and widely used public-key cryptosystem in the world today. Compared to other public-key cryptosystems, such as elliptic curve cryptography, RSA requires longer keylengths and is computationally more expensive. In order to address these shortcomings, many variants of RSA have been proposed over the years. While the security of RSA has been well studied since it was proposed in 1977, many of these variants have not. In this thesis, we investigate the security of five of these variants of RSA. In particular, we provide detailed analyses of the best known algebraic attacks (including some new attacks) on instances of RSA with certain special private exponents, multiple instances of RSA sharing a common small private exponent, Multi-prime RSA, Common Prime RSA and Dual RSA.

No description available.

The rapid increase in the use of embedded systems for performing secure transactions, has proportionally increased the security threats which are faced by such devices. Side channel attack, a sophisticated security threat to embedded devices like smartcards, mobile phones and PDAs, exploits the external manifestations like processing time, power consumption and electromagnetic emission to identify the internal computations. Power analysis attack, introduced by Kocher in 1998, is used by adversaries to eavesdrop on confidential data while the device is executing a secure transaction. The adversary observes the power trace dissipated/consumed by the chip during the encryption/decryption of the AES cryptographic program and predicts the secret key used for encryption by extracting necessary information from the power trace. Countermeasures proposed to overcome power analysis are data masking, table masking, current flattening, circuitry level solutions, dummy instruction insertions, balancing bit-flips, etc. All these techniques are either susceptible to multi-order side channel attacks, not sufficiently generic to cover all encryption algorithms, or burden the system with high area cost, run-time or energy consumption. The initial solution presented in this thesis is a HW/SW based randomised instruction injection technique, which infuses random instructions at random places during the execution of an application. Such randomisation obfuscates the secure information from the power profile, not allowing the adversary to extract the critical power segments for analysis. Further, the author devised a systematic method to measure the security level of a power sequence and used it to measure the number of random instructions needed, to suitably confuse the adversary. The proposed processor model costs 1.9% in additional area for a simplescalar processor, and costs on average 29.8% in runtime and 27.1% in additional energy consumption for six industry standard cryptographic algorithms. This design is extended to a processor architecture which automatically detects the execution of the most common encryption algorithms, starts to scramble the power waveform by adding randomly placed instructions with random register accesses, and stops injecting instructions when it is safe to do so. This approach has less overheads compared to previous solutions and avoids software instrumentation, allowing programmers with no special knowledge to use the system. The extended processor model costs an additional area of 1.2%, and an average of 25% in runtime and 28.5% in energy overheads for industry standard cryptographic algorithms. Due to the possibility of removing random injections using large number of samples (due to the random nature, a large number of samples will eliminate noise), the author proposes a multiprocessor 'algorithmic' balancing technique. This technique uses a dual processor architecture where two processors execute the same program in parallel, but with complementary intermediate data, thus balancing the bitflips. The second processor works in conjunction with the first processor for balancing only when encryption is performed, and both processors carry out independent tasks when no encryption is being performed. Both DES and AES cryptographic programs are investigated for balancing and the author shows that this technique is economical, while completely preventing power analysis attacks. The signature detection unit to capture encryption is also utilised, which is used in the instruction injection approach. This multiprocessor balancing approach reduces performance by 0.42% and 0.94% for AES and DES respectively. The hardware increase is 2X only when balancing is performed. Further, several future extensions for the balancing approach are proposed, by introducing random swapping of encryption iterations between cores. FPGA implementations of these processor designs are briefly described at the end of this thesis.

Security of a Multi-Processor System on Chip (MPSoC) is an emerging area of concern in embedded systems. MPSoC security is jeopardized by Code Injection attacks. Code Injection attacks, which are the most common types of software attacks, have plagued single processor systems. Design of MPSoCs must therefore incorporate security as one of the primary objectives. Code Injection attacks exploit vulnerabilities in \trusted" and legacy code. An architecture with a dedicated monitoring processor (MONITOR) is employed to simultaneously supervise the application processors on an MPSoC. The program code in the application processors is divided into basic blocks. The basic blocks in the application processors are statically instrumented with special instructions that allow communication with the MONITOR at runtime. The MONITOR verifies the execution of all the processors at runtime using control flow checks and either a timing or instruction count check. This thesis proposes a monitoring system called SOFTMON, a design methodology called SHIELD, a design flow called LOCS and an architectural framework called CUFFS for detecting Code Injection attacks. SOFTMON, a software monitoring system, uses a software algorithm in the MONITOR. SOFTMON incurs limited area overheads. However, the runtime performance overhead is quite high. SHIELD, an extension to the work in SOFTMON overcomes the limitation of high runtime overhead using a MONITOR that is predominantly hardware based. LOCS uses only one special instruction per basic block compared to two, as was the case in SOFTMON and SHIELD. Additionally, profile information is generated for all the basic blocks in all the application processors for the MPSoC designer to tune the design by increasing or decreasing the frequency of loop basic blocks. CUFFS detects attacks even without application processors communicating to the MONITOR. The SOFTMON, SHIELD and LOCS approaches can only detect attacks if the application processors communicate to the MONITOR. CUFFS relies on the exact number of instructions in basic blocks to determine an attack, rather than time-frame based measures used in SOFTMON, SHIELD and LOCS. The lowest runtime performance overhead was achieved by LOCS (worst case of 37.5%), while the SOFTMON monitoring system had the least amount of area overheads of about 25%. The CUFFS approach employed an active MONITOR and hence detected a greater range of attacks. The CUFFS framework also detects bit flip errors (reliability errors) in the control flow instructions of the application processors on an MPSoC. CUFFS can detect nearly 70% of all bit flip errors in the control flow instructions. Additionally, a modified CUFFS approach is proposed to ensure reliable inter-processor communication on an MPSoC. The modified CUFFS approach uses a hardware based checksum approach for reliable inter-processor communication and incurred a runtime performance overhead of up to 25% and negligible area overheads compared to CUFFS. Thus, the approaches proposed in this thesis equip an MPSoC designer with tools to embed security features during an MPSoC's design phase. Incorporating security measures at the processor design level provides security against software attacks in MPSoCs and incurs manageable runtime, area and code-size overheads.

Final Project (M.A.)--John F. Kennedy University, 2004. / "August 30, 2004"--T.p. Includes bibliographical references (p. 181-192).

Thesis (M.S.)--Virginia Polytechnic Institute and State University, 1993. / Vita. Abstract. Includes bibliographical references (leaves 74-84). Also available via the Internet.

Thesis (Ph. D.)--University of Nevada, Reno, 2008. / "August, 2008." Includes bibliographical references (leaves 93-112). Online version available on the World Wide Web.

Thesis (Ph. D.)--Lehigh University, 2005. / Includes vita. Includes bibliographical references (leaves 107-114).

Dissertation (Ph.D.)--University of Toledo, 2005. / Typescript. "Submitted as partial fulfillment of the requirements for the Doctor of Philosophy in Psychology." "A dissertation entitled"--at head of title. Title from title page of PDF document. Bibliography: p. 211-241.

Algebraic attacks constitute an effective class of cryptanalytic attacks which have come up recently. In algebraic attacks, the relations between the input, output and the key are expressed as a system of equations and then solved for the key. The main idea is in obtaining a system of equations which is solvable using reasonable amount of resources. The new approaches proposed in this work and experimental studies on the existing algebraic attacks on stream ciphers will be presented. In the first attack on filter generator, the input-output relations are expressed in conjunctive normal form. The system of equations is then solved using modified Zakrevskij technique. This was one of the earliest algebraic attacks on the nonlinear filter generator. In the second attack, we relaxed the constraint on algebraic attack that the entire system description be known and the output sequence extension problem where the filter function is unknown is considered. We modeled the problem as a multivariate interpolation problem and solved it. An advantage of this approach is that it can be adapted to work for noisy output sequences where as the existing algebraic attacks expect the output sequence to be error free. Adding memory to filter/combiner function increases the degree of system of equations and finding low degree equations in this case is computeintensive. The method for computing low degree relations for combiners with memory was applied to the combiner in E0 stream cipher. We found that the relation given in literature [Armknecht and Krause] was incorrect. We obtained the correct equation and verified its correctness. A time-data size trade off attack for clock controlled filter generator was developed. The time complexity and the data requirements are in between the two approaches used in literature. A recent development of algebraic attacks - the Cube attack was studied. Cube attack on variants of Trivium were proposed by Dinur and Shamir where linear equations in key bits were obtained by combining equations for output bit for same key and a set of Initialization Vectors (IVs). We investigated the effectiveness of the cube attack on Trivium. We showed that the linear equations obtained were not general and hence the attack succeeds only for some specific values of IVs. A reason for the equations not being general is given and a modification to the linear equation finding step suggested.