Adi Shamir

Adi Shamir (Hebrew: עדי שמיר‎; born July 6, 1952) is an Israeli cryptographer. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identification scheme (along with Uriel Feige and Amos Fiat), one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer science.[3]

Adi Shamir
Adi Shamir Royal Society
Adi Shamir at the Royal Society admissions day in London, July 2018
BornJuly 6, 1952 (age 66)
ResidenceIsrael
Alma materTel Aviv University
Weizmann Institute of Science
Known forRSA
Feige–Fiat–Shamir identification scheme
differential cryptanalysis
Awards
Scientific career
FieldsCryptography
InstitutionsWeizmann Institute
University of Warwick
ThesisFixed Points of Recursive Programs and their Relation in Differential Agard Calculus (1977)
Doctoral advisorZohar Manna[2]
Doctoral studentsEli Biham
Uriel Feige
Amos Fiat[2]
Websitewww.wisdom.weizmann.ac.il/profile/scientists/shamir-profile.html

Education

Born in Tel Aviv, Shamir received a Bachelor of Science (BSc) degree in mathematics from Tel Aviv University in 1973 and obtained his Master of Science (MSc) and Doctor of Philosophy (PhD) degrees in Computer Science from the Weizmann Institute in 1975 and 1977 respectively.[2]

Career and research

After a year as a postdoctoral researcher at the University of Warwick, he did research at Massachusetts Institute of Technology (MIT) from 1977–1980 before returning to be a member of the faculty of Mathematics and Computer Science at the Weizmann Institute. Starting from 2006, he is also an invited professor at École Normale Supérieure in Paris.

In addition to RSA, Shamir's other numerous inventions and contributions to cryptography include the Shamir secret sharing scheme, the breaking of the Merkle-Hellman knapsack cryptosystem, visual cryptography, and the TWIRL and TWINKLE factoring devices. Together with Eli Biham, he discovered differential cryptanalysis, a general method for attacking block ciphers. It later emerged that differential cryptanalysis was already known — and kept a secret — by both IBM[4] and the National Security Agency (NSA).[5]

Shamir has also made contributions to computer science outside of cryptography, such as finding the first linear time algorithm for 2-satisfiability[6] and showing the equivalence of the complexity classes PSPACE and IP.

Awards and honors

Shamir has received a number of awards, including the following:

References

  1. ^ a b Anon (2018). "Adi Shamir ForMemRS". royalsociety.org. London: Royal Society. Retrieved 2018-07-22. One or more of the preceding sentences incorporates text from the royalsociety.org website where:

    “All text published under the heading 'Biography' on Fellow profile pages is available under Creative Commons Attribution 4.0 International License.” --Royal Society Terms, conditions and policies at the Wayback Machine (archived 2016-11-11)

  2. ^ a b c Adi Shamir at the Mathematics Genealogy Project
  3. ^ Adi Shamir at DBLP Bibliography Server Edit this at Wikidata
  4. ^ Coppersmith, Don (May 1994). "The Data Encryption Standard (DES) and its strength against attacks" (PDF). IBM Journal of Research and Development. 38 (3): 243. doi:10.1147/rd.383.0243. Archived (PDF) from the original on 2007-06-15. (subscription required)
  5. ^ Levy, Steven (2001). Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age. Penguin Books. pp. 55–56. ISBN 0-14-024432-8.
  6. ^ Even, S.; Itai, A.; Shamir, A. (1976), "On the complexity of time table and multi-commodity flow problems", SIAM Journal on Computing, 5 (4): 691–703, doi:10.1137/0205048.
  7. ^ "A. M. Turing Award". Association for Computing Machinery. Archived from the original on 2009-12-12. Retrieved February 5, 2011.
  8. ^ "Archived copy". Archived from the original on 2009-04-06. Retrieved 2009-02-17.CS1 maint: Archived copy as title (link)
  9. ^ "IEEE W.R.G. Baker Prize Paper Award Recipients" (PDF). IEEE. Archived from the original (PDF) on 2011-04-25. Retrieved February 5, 2011.
  10. ^ "IEEE Koji Kobayashi Computers and Communications Award Recipients" (PDF). IEEE. Archived from the original (PDF) on 2010-11-24. Retrieved February 15, 2011.
  11. ^ "Israel Prize Official Site (in Hebrew) - Recipient's C.V." Archived from the original on 2012-09-10.
  12. ^ "Israel Prize Official Site (in Hebrew) - Judges' Rationale for Grant to Recipient". Archived from the original on 2012-09-10.
  13. ^ "Presentation of the honorary degree at the Fall 2009 Convcation" (PDF). Archived from the original (PDF) on 2011-09-24. Retrieved October 31, 2011.
  14. ^ "Laureates of the Japan Prize". Archived from the original on 2017-02-04.
Aircrack-ng

Aircrack-ng is a network software suite consisting of a detector, packet sniffer, WEP and WPA/WPA2-PSK cracker and analysis tool for 802.11 wireless LANs. It works with any wireless network interface controller whose driver supports raw monitoring mode and can sniff 802.11a, 802.11b and 802.11g traffic. The program runs under Linux, FreeBSD, OS X, OpenBSD, and Windows; the Linux version is packaged for OpenWrt and has also been ported to the Android, Zaurus PDA and Maemo platforms; and a proof of concept port has been made to the iPhone.

In April 2007 a team at the Darmstadt University of Technology in Germany developed a new attack method based on a paper released on the RC4 cipher by Adi Shamir. This new attack, named 'PTW', decreases the number of initialization vectors or IVs needed to decrypt a WEP key and has been included in the aircrack-ng suite since the 0.9 release.

Aircrack-ng is a fork of the original Aircrack project. It can be found as a preinstalled tool in many Linux distributions such as Kali Linux or Parrot, which share common attributes as they are developed under the same project(Debian).

Alex Biryukov

Alex Biryukov is a cryptographer, currently a full professor at the University of Luxembourg. His notable work includes the design of the stream cipher LEX, as well as the cryptanalysis of numerous cryptographic primitives. In 1998, he developed impossible differential cryptanalysis together with Eli Biham and Adi Shamir. In 1999, he developed the slide attack together with David Wagner. In 2009 he developed, together with Dmitry Khovratovich, the first cryptanalytic attack on full-round AES-192 and AES-256 that is faster than a brute-force attack. In 2015 he developed the Argon2 key derivation function with Daniel Dinu and Dmitry Khovratovich.

Since 1994 Alex Biryukov is a member of the International Association for Cryptologic Research.

Differential cryptanalysis

Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can affect the resultant difference at the output. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformation, discovering where the cipher exhibits non-random behavior, and exploiting such properties to recover the secret key (cryptography key).

Eli Biham

Eli Biham (Hebrew: אלי ביהם‎) is an Israeli cryptographer and cryptanalyst, currently a professor at the Technion Israeli Institute of Technology Computer Science department. Starting from October 2008 and till 2013, Biham was the dean of the Technion Computer Science department, after serving for two years as chief of CS graduate school.

Biham received his Ph.D. for inventing (publicly) differential cryptanalysis, while working under Adi Shamir. It had, it turned out, been invented at least twice before. A team at IBM discovered it during their work on DES, and was requested/required to keep their discovery secret by the NSA, who evidently knew about it as well.

FEAL

In cryptography, FEAL (the Fast data Encipherment ALgorithm) is a block cipher proposed as an alternative to the Data Encryption Standard (DES), and designed to be much faster in software. The Feistel based algorithm was first published in 1987 by Akihiro Shimizu and Shoji Miyaguchi from NTT. The cipher is susceptible to various forms of cryptanalysis, and has acted as a catalyst in the discovery of differential and linear cryptanalysis.

There have been several different revisions of FEAL, though all are Feistel ciphers, and make use of the same basic round function and operate on a 64-bit block. One of the earliest designs is now termed FEAL-4, which has four rounds and a 64-bit key.

Problems were found with FEAL-4 from the start: Bert den Boer related a weakness in an unpublished rump session at the same conference where the cipher was first presented. A later paper (den Boer, 1988) describes an attack requiring 100–10000 chosen plaintexts, and Sean Murphy (1990) found an improvement that needs only 20 chosen plaintexts. Murphy and den Boer's methods contain elements similar to those used in differential cryptanalysis.

The designers countered by doubling the number of rounds, FEAL-8 (Shimizu and Miyaguchi, 1988). However, eight rounds also proved to be insufficient — in 1989, at the Securicom conference, Eli Biham and Adi Shamir described a differential attack on the cipher, mentioned in (Miyaguchi, 1989). Gilbert and Chassé (1990) subsequently published a statistical attack similar to differential cryptanalysis which requires 10000 pairs of chosen plaintexts.

In response, the designers introduced a variable-round cipher, FEAL-N (Miyaguchi, 1990), where "N" was chosen by the user, together with FEAL-NX, which had a larger 128-bit key. Biham and Shamir's differential cryptanalysis (1991) showed that both FEAL-N and FEAL-NX could be broken faster than exhaustive search for N ≤ 31. Later attacks, precursors to linear cryptanalysis, could break versions under the known plaintext assumption, first (Tardy-Corfdir and Gilbert, 1991) and then (Matsui and Yamagishi, 1992), the latter breaking FEAL-4 with 5 known plaintexts, FEAL-6 with 100, and FEAL-8 with 215.

In 1994, Ohta and Aoki presented a linear cryptanalytic attack against FEAL-8 that required 212 known plaintexts.

GDES

In cryptography, the Generalized DES Scheme (GDES or G-DES) is a variant of the DES symmetric-key block cipher designed with the intention of speeding up the encryption process while improving its security. The scheme was proposed by Ingrid Schaumuller-Bichl in 1981.

In 1990, Eli Biham and Adi Shamir showed that GDES was vulnerable to differential cryptanalysis, and that any GDES variant faster than DES is also less secure than DES.

GDES generalizes the Feistel network structure of DES to larger block sizes. In each round, the DES round function is applied to the rightmost 32-bit subblock, and the result is XORed with all the other parts. Then the block is rotated 32 bits to the right.

Geometric cryptography

Geometric cryptography is an area of cryptology where messages and ciphertexts are represented by geometric quantities such as angles or intervals and where computations are performed by ruler and compass constructions. The difficulty or impossibility of solving certain geometric problems like trisection of an angle using ruler and compass only is the basis for the various protocols in geometric cryptography. This field of study was suggested by Mike Burmester, Ronald L. Rivest and Adi Shamir in 1996. Though the cryptographic methods based on geometry have practically no real life applications, they are of use as pedagogic tools for the elucidation of other more complex cryptographic protocols.

ID-based cryptography

Identity-based cryptography is a type of public-key cryptography in which a publicly known string representing an individual or organization is used as a public key. The public string could include an email address, domain name, or a physical IP address.

The first implementation of identity-based signatures and an email-address based public-key infrastructure (PKI) was developed by Adi Shamir in 1984, which allowed users to verify digital signatures using only public information such as the user's identifier. Under Shamir's scheme, a trusted third party would deliver the private key to the user after verification of the user's identity, with verification essentially the same as that required for issuing a certificate in a typical PKI.

Shamir similarly proposed identity-based encryption, which appeared particularly attractive since there was no need to acquire an identity's public key prior to encryption. However, he was unable to come up with a concrete solution, and identity-based encryption remained an open problem for many years. The first practical implementations were finally devised by Sakai in 2000, and Boneh and Franklin in 2001. These solutions were based on bilinear pairings. Also in 2001, a solution was developed independently by Clifford Cocks.

Impossible differential cryptanalysis

In cryptography, impossible differential cryptanalysis is a form of differential cryptanalysis for block ciphers. While ordinary differential cryptanalysis tracks differences that propagate through the cipher with greater than expected probability, impossible differential cryptanalysis exploits differences that are impossible (having probability 0) at some intermediate state of the cipher algorithm.

Lars Knudsen appears to be the first to use a form of this attack, in the 1998 paper where he introduced his AES candidate, DEAL. The first presentation to attract the attention of the cryptographic community was later the same year at the rump session of CRYPTO '98, in which Eli Biham, Alex Biryukov, and Adi Shamir introduced the name "impossible differential" and used the technique to break 4.5 out of 8.5 rounds of IDEA and 31 out of 32 rounds of the NSA-designed cipher Skipjack. This development led cryptographer Bruce Schneier to speculate that the NSA had no previous knowledge of impossible differential cryptanalysis. The technique has since been applied to many other ciphers: Khufu and Khafre, E2, variants of Serpent, MARS, Twofish, Rijndael, CRYPTON, Zodiac, Hierocrypt-3, TEA, XTEA, Mini-AES, ARIA, Camellia, and SHACAL-2.

Biham, Biryukov and Shamir also presented a relatively efficient specialized method for finding impossible differentials that they called a miss-in-the-middle attack. This consists of finding "two events with probability one, whose conditions cannot be met together."

KASUMI

KASUMI is a block cipher used in UMTS, GSM, and GPRS mobile communications systems.

In UMTS, KASUMI is used in the confidentiality (f8) and integrity algorithms (f9) with names UEA1 and UIA1, respectively.

In GSM, KASUMI is used in the A5/3 key stream generator and in GPRS in the GEA3 key stream generator.

KASUMI was designed for 3GPP to be used in UMTS security system by the Security Algorithms Group of Experts

(SAGE), a part of the European standards body ETSI.

Because of schedule pressures in 3GPP standardization, instead of developing a new cipher, SAGE agreed with

3GPP technical specification group (TSG) for system aspects of 3G security (SA3) to base the development

on an existing algorithm that had already undergone some evaluation.

They chose the cipher algorithm MISTY1 developed

and patented

by Mitsubishi Electric Corporation.

The original algorithm was slightly modified for easier hardware implementation and to

meet other requirements set for 3G mobile communications security.

KASUMI is named after the original algorithm MISTY1 — 霞み (hiragana かすみ, romaji kasumi) is the Japanese word for "mist".

In January 2010, Orr Dunkelman, Nathan Keller and Adi Shamir released a paper showing that they could break Kasumi with a related-key attack and very modest computational resources; this attack is ineffective against MISTY1.

Moni Naor

Moni Naor (Hebrew: מוני נאור‎) is an Israeli computer scientist, currently a professor at the Weizmann Institute of Science. Naor received his Ph.D. in 1989 at the University of California, Berkeley. His advisor was Manuel Blum.

He works in various fields of computer science, mainly the foundations of cryptography. He is notable for initiating research on public key systems secure against chosen ciphertext attack and creating non-malleable cryptography, visual cryptography (with Adi Shamir), and suggesting various methods for verifying that users of a computer system are human (leading to the notion of CAPTCHA). His research on Small-bias sample space, give a general framework for combining small k-wise independent spaces with small -biased spaces to obtain -almost k-wise independent spaces of small size. In 1994 he was the first, with Amos Fiat, to formally study the problem of practical broadcast encryption. Along with Benny Chor, Amos Fiat, and Benny Pinkas, he made a contribution to the development of Traitor tracing, a copyright infringement detection system which works by tracing the source of leaked files rather than by direct copy protection.

N-Hash

In cryptography, N-Hash is a cryptographic hash function based on the FEAL round function, and is now considered insecure. It was proposed in 1990 by Miyaguchi et al.; weaknesses were published the following year.

N-Hash has a 128-bit hash size. A message is divided into 128-bit blocks, and each block is combined with the hash value computed so far using the g compression function. g contains eight rounds, each of which uses an F function, similar to the one used by FEAL.

Eli Biham and Adi Shamir (1991) applied the technique of differential cryptanalysis to N-Hash, and showed that collisions could be generated faster than by a birthday attack for N-Hash variants with even up to 12 rounds.

RSA Security

RSA Security LLC, formerly RSA Security, Inc. and doing business as RSA, is an American computer and network security company. RSA was named after the initials of its co-founders, Ron Rivest, Adi Shamir and Leonard Adleman, after whom the RSA public key cryptography algorithm was also named. Among its products are the RSA BSAFE cryptography libraries and the SecurID authentication token. RSA is known for allegedly incorporating backdoors developed by the NSA in its products. It also organizes the annual RSA Conference, an information security conference.

Founded as an independent company in 1982, RSA Security was acquired by EMC Corporation in 2006 for US$2.1 billion and operated as a division within EMC. When EMC was acquired by Dell Technologies in 2016, RSA became part of the Dell Technologies family of brands.

RSA is based in Bedford, Massachusetts, with regional headquarters in Bracknell (UK) and Singapore, and numerous international offices.

Ron Rivest

Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL). He was a member of the Election Assistance Commission's Technical Guidelines Development Committee, tasked with assisting the EAC in drafting the Voluntary Voting System Guidelines.Rivest is one of the inventors of the RSA algorithm (along with Adi Shamir and Len Adleman). He is the inventor of the symmetric key encryption algorithms RC2, RC4, RC5, and co-inventor of RC6. The "RC" stands for "Rivest Cipher", or alternatively, "Ron's Code". (RC3 was broken at RSA Security during development; similarly, RC1 was never published.) He also authored the MD2, MD4, MD5 and MD6 cryptographic hash functions. In 2006, he published his invention of the ThreeBallot voting system, a voting system that incorporates the ability for the voter to discern that their vote was counted while still protecting their voter privacy. Most importantly, this system does not rely on cryptography at all. Stating "Our democracy is too important", he simultaneously placed ThreeBallot in the public domain.

Rivest frequently collaborates with other researchers in combinatorics, for example working with David A. Klarner to find an upper bound on the number of polyominoes of a given order and working with Jean Vuillemin to prove the deterministic form of the Aanderaa–Rosenberg conjecture.

Snefru

Snefru is a cryptographic hash function invented by Ralph Merkle in 1990 while working at Xerox PARC. The function supports 128-bit and 256-bit output. It was named after the Egyptian Pharaoh Sneferu, continuing the tradition of the Khufu and Khafre block ciphers.

The original design of Snefru was shown to be insecure by Eli Biham and Adi Shamir who were able to use differential cryptanalysis to find hash collisions. The design was then modified by increasing the number of iterations of the main pass of the algorithm from two to eight. Although differential cryptanalysis can break the revised version with less complexity than brute force search (a certificational weakness), the attack requires operations and is thus not currently feasible in practice.

Steganographic file system

Steganographic file systems are a kind of file system first proposed by Ross Anderson, Roger Needham, and Adi Shamir. Their paper proposed two main methods of hiding data: in a series of fixed size files originally consisting of random bits on top of which 'vectors' could be superimposed in such a way as to allow levels of security to decrypt all lower levels but not even know of the existence of any higher levels, or an entire partition is filled with random bits and files hidden in it.

In a steganographic file system using the second scheme, files are not merely stored, nor stored encrypted, but the entire partition is randomized - encrypted files strongly resemble randomized sections of the partition, and so when files are stored on the partition, there is no easy way to discern between meaningless gibberish and the actual encrypted files. Furthermore, locations of files are derived from the key for the files, and the locations are hidden and available to only programs with the passphrase. This leads to the problem that very quickly files can overwrite each other (because of the Birthday Paradox); this is compensated for by writing all files in multiple places to lessen the chance of data loss.

TWIRL

In cryptography and number theory, TWIRL (The Weizmann Institute Relation Locator) is a hypothetical hardware device designed to speed up the sieving step of the general number field sieve integer factorization algorithm. During the sieving step, the algorithm searches for numbers with a certain mathematical relationship. In distributed factoring projects, this is the step that is parallelized to a large number of processors.

TWIRL is still a hypothetical device — no implementation has been publicly reported. However, its designers, Adi Shamir and Eran Tromer, estimate that if TWIRL were built, it would be able to factor 1024-bit numbers in one year at the cost of "a few dozen million US dollars". TWIRL could therefore have enormous repercussions in cryptography and computer security — many high-security systems still use 1024-bit RSA keys, which TWIRL would be able to break in a reasonable amount of time and for reasonable costs.

The security of some important cryptographic algorithms, notably RSA and the Blum Blum Shub pseudorandom number generator, rests in the difficulty of factorizing large integers. If factorizing large integers becomes easier, users of these algorithms will have to resort to using larger keys (computationally more expensive) or to using different algorithms, whose security rests on some other computationally hard problem (like the discrete logarithm problem).

Uriel Feige

Uriel Feige (Hebrew: אוריאל פייגה‎) is an Israeli computer scientist who was a doctoral student of Adi Shamir.

Visual cryptography

Visual cryptography is a cryptographic technique which allows visual information (pictures, text, etc.) to be encrypted in such a way that the decrypted information appears as a visual image.

One of the best-known techniques has been credited to Moni Naor and Adi Shamir, who developed it in 1994. They demonstrated a visual secret sharing scheme, where an image was broken up into n shares so that only someone with all n shares could decrypt the image, while any n − 1 shares revealed no information about the original image. Each share was printed on a separate transparency, and decryption was performed by overlaying the shares. When all n shares were overlaid, the original image would appear. There are several generalizations of the basic scheme including k-out-of-n visual cryptography.Using a similar idea, transparencies can be used to implement a one-time pad encryption, where one transparency is a shared random pad, and another transparency acts as the ciphertext. Normally, there is an expansion of space requirement in visual cryptography. But if one of the two shares is structured recursively, the efficiency of visual cryptography can be increased to 100%.Some antecedents of visual cryptography are in patents from the 1960s. Other antecedents are in the work on perception and secure communication.Visual cryptography can be used to protect biometric templates in which decryption does not require any complex computations.

This page is based on a Wikipedia article written by authors (here).
Text is available under the CC BY-SA 3.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.