Cryptography E-Book

Zoubir Z. Mammeri

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 1338

Veröffentlichungsjahr: 2024

Beschreibung

Cryptography An introduction to one of the backbones of the digital world Cryptography is one of the most important aspects of information technology security, central to the protection of digital assets and the mitigation of risks that come with increased global connectivity. The digital world is wholly reliant on secure algorithms and protocols for establishing identity, protecting user data, and more. Groundbreaking recent developments in network communication and a changing digital landscape have been accompanied by similar advances in cryptography, which is more central to digital life than ever before. This book constitutes a comprehensive yet accessible introduction to the algorithms, protocols, and standards which protect the modern internet. Built around both foundational theories and hundreds of specific algorithms, it also incorporates the required skills in complex mathematics. The result is an indispensable introduction to the protocols and systems which should define cryptography for decades to come. Readers will also find: * Over 450 problems with accompanying solutions to reinforce key concepts and test retention * Detailed discussion of topics including symmetric and asymmetric algorithms, random number generation, user authentication, and many more * Over 200 figures and tables that provide rich detail to the content Cryptography: Algorithms, Protocols, and Standards for Computer Security is ideal for undergraduate and graduate students in cryptography and information technology subjects, as well as for researchers looking for a working reference on existing cryptographic algorithms and protocols.

Leseprobe

Cryptography

Algorithms, Protocols, and Standards for Computer Security

Zoubir Mammeri

Copyright © 2024 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.

Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Trademarks: Wiley and the Wiley logo are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates in the United States and other countries and may not be used without written permission. All other trademarks are the property of their respective owners. John Wiley & Sons, Inc. is not associated with any product or vendor mentioned in this book.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Names: Mammeri, Zoubir, author. | John Wiley & Sons, publisher.

Title: Cryptography : algorithms, protocols, and standards for computer security / Zoubir Mammeri.

Description: Hoboken, New Jersey : JW-Wiley, [2024] | Includes bibliographical references and index.

Identifiers: LCCN 2023030470 | ISBN 9781394207480 (hardback) | ISBN 9781394207497 (pdf) | ISBN 9781394207503 (epub) | ISBN 9781394207510 (ebook)

Subjects: LCSH: Cryptography. | Computer security.

Classification: LCC QA268 .M34 2024 | DDC 005.8/24--dc23/eng/20230807

LC record available at https://lccn.loc.gov/2023030470

Cover Design: Wiley

Cover Image: © zf L/Getty Images

Set in 9.5/12.5pt STIXTwoText by Integra Software Services Pvt. Ltd, Pondicherry, India

Preface

For millennia, human beings have used multiple forms of codes to protect their oral communications, entries of castles, their messages, and other belongings. Indeed, cryptography existed early in human history and civilizations, before the event of computers. Cryptography has been developed and improved over the centuries, in particular for protecting military secrets and spying on enemies, then for protecting industrial and economical secrets, then for protecting recent applications made possible with the use of the internet, and ultimately for protecting the privacy of electronic devices’ users. In a highly computerized world, cryptography is the pillar of security. Encrypting and signing are the most performed cryptographic operations in the digital world.

Cryptography provides services to secure websites, electronic transmissions, and data repositories. For more than three decades, public-key cryptography has been enabling people, who never met before, to securely communicate and trust each other. Cryptography is not only used over the internet, but also in phones, bank cards, televisions, cars, aircrafts, door locks, implants, and a variety of other devices. Without cryptography, hackers could get into victims’ emails, listen to their phone conversations, tap into their cable companies and acquire free cable services, or break into their bank accounts.

Cryptography is the discipline at the intersection of computer science and mathematics. It provides algorithms for guaranteeing confidentiality, integrity, authentication, and non-repudiation for parties that share data or exchange messages to perform operations and transactions in cyberspace. For example, customers’ bank accounts or citizens’ votes must remain confidential and not altered by any unauthorized third party. E-merchants, as well as clients, must be protected from each other; a customer, who ordered an article, could not deny ordering; and a merchant, who has been paid, could not deny having been. A person, who digitally signed an agreement or a contract, cannot deny having signed. Such protections, and many others, are provided thanks to cryptography.

Cryptography standards are needed to enable interoperability in cyberspace. In general, standard protocols follow rigorous procedures of testing before their adoption. Therefore, it is highly recommended to use only standard security protocols to build information security systems. Security, in general, and cryptography, in particular, have evolved at a rapid pace in the past two decades. Security technology has gone through tremendous changes in terms of protocols and standards. The continuous evolution of information technology, on one hand, and the discovery of vulnerabilities in standards, on the other hand, motivate the development of new standards. In the last 15 years, cryptography standards made tremendous advances that are not included in existing books. Some standards have become obsolete and others have recently been recommended. This book aims at providing a comprehensive description of recent advances in cryptographic protocols. The focus is on the NIST (National Institute for Standards and Technology, US) and IETF (Internet Engineering Task Force) standards, which are commonly used in the internet and networking applications.

This book, also, aims at providing a comprehensive description of notions, algorithms, protocols, and standards in the cryptographic field. It addresses algorithms through examples and problems, highlights vulnerabilities of deprecated standards, and describes in detail algorithms and protocols recommended in recent standards. In addition, it focuses on the basic notions and methods of security analysis and cryptanalysis of symmetric ciphers. The book is designed to serve as a textbook for undergraduate and graduate students, as well as a reference for researchers and practitioners in cryptography.

Definitions Used in the Book

Definitions included in this book are inspired by NIST and IETF glossaries [1,2]. They are not formal definitions. Rather, they are provided to summarize the basic notions of cryptography and facilitate the learning of algorithms and protocols.

Paulsen C, Byers RD. Glossary of Key Information Security Terms. NIST; 2019.

Shirey R. Internet Security Glossary, RFC 4949. Internet Engineering Task Force; 2007.

Organization of the Book

Chapter 1: This chapter introduces aims at introducing the main issues and notions of security in computer-based systems. The main properties of security (namely confidentiality, integrity, authenticity, and non-repudiation) are introduced. A taxonomy of attacks on digital assets is provided. Multiple components and practices, required to address from different perspectives the security of computer-based systems, are introduced in this chapter. The main technical components of security include cryptography, which is the focus of the remainder of the book.

Chapter 2: Cryptography has developed and improved over time. Chapter 2 aims at providing a brief history of cryptography and presenting its main notions and techniques. Breaking cryptographic codes is a very ancient activity to disclose secrets. An overall categorization of attacks on modern cryptographic algorithms is discussed in this chapter. There exist two main categories of cryptographic systems: symmetric and asymmetric (also called public-key) cryptosystems. The design differences between both categories are briefly discussed. Message digest, digital signature, and digital certificate are of prime importance to establish trust between parties that share data and exchange messages. These notions are introduced in Chapter 2.

Chapter 3: This chapter aims at reviewing and presenting, with examples and exercises, the mathematical background useful to address cryptography algorithms. In particular, modular arithmetic and finite fields are of prime importance to understand the design of cryptographic algorithms. Fundamental theorems for cryptography are provided. In addition, to mathematical notions, computation algorithms (such as Extended Euclidean algorithm, square-and-multiply method to perform modular exponentiation, modular multiplication, Gauss’s algorithm to solve congruence systems, Tonelli-Shanks’s algorithm to find modular square roots, and Rabin’s algorithm to test irreducibility of polynomials), which are often used in cryptographic algorithms, are introduced with examples and exercises. Readers who have a sufficient background in the reminded notions and algorithms can skip this chapter.

Chapter 4: Shift and substitution ciphers have been used in written text transmission; and dominated the art of secret writing for at least two millenniums. The most known historical ciphers in this category include Caesar’s, Vigenere’s, Affine, One Time Pad, and Enigma ciphers. All those ciphers are original inventions, with ideas and principles that inspired authors of modern cryptographic algorithms. Before presenting modern cryptographic algorithms, Chapter 4 aims at providing an overview of historical ciphers and their ingenious ideas. Methods used to break historical ciphers have widely been exploited to design modern ciphers.

Chapter 5: This chapter introduces three notions of cryptography: hash functions, message authentication codes, and digital signature. All of them are of paramount importance for providing integrity and authentication guarantees. Hash functions produce digital fingerprints, also called message tags, which are mainly used to verify the integrity of messages and files, to generate and verify digital signatures, and to generate random numbers. Approaches to design hash functions and standard hash functions (i.e. SHA-1, SHA-2, and SHA-3) and standard Message Authentication Codes (i.e. HMAC and KMAC) are described in detail. Common attacks against MAC algorithms and digital signatures are discussed.

Chapter 6: Stream ciphers are symmetric ciphers that encrypt and decrypt bits individually. They are used, in particular, to secure communications in wireless and cellular networks. Stream ciphers are well-suited to hardware implementation and they are generally faster than block ciphers. They also are well-suited to encrypt and decrypt continuous data at high rate and when devices have limited memory to store long messages. Often, stream ciphers are designed using LFSRs (Linear-Feedback Shift Registers) combined with nonlinear filtering functions. Chapter 6 aims at providing a discussion of the design principles of LFSRs and stream ciphers to produce keystream bits, used to encrypt plaintexts and decrypt ciphertexts. It also provides a detailed description of the most known and standard stream ciphers: A5/1, E0, SNOW 3G, ZUC, Chacha20, RC4, Trivium, and Enocoro.

Chapter 7: This chapter addresses block ciphers, which are the most used algorithms to secure data and messages. Data or messages are split into blocks of a fixed size (e.g. 128 bits) and plaintext blocks are encrypted individually to generate ciphertext blocks of the same bit-length than that of a plaintext block. In addition to ciphering, block ciphers can be used to generate pseudorandom numbers or to build hash functions and MACs (Message Authentication Codes). A huge number of block ciphers are published in literature. However, a very small number of them are standards that are used in operational cryptosystems. This chapter introduces the basics of construction of block ciphers and presents in detail the standard block ciphers, currently in use, namely TDEA (Triple Data Encryption Algorithm) and AES (Advanced Encryption Standard). Known attacks against block ciphers are discussed.

Chapters 8 and 9: A block cipher, such as AES or TDEA, takes a fixed-size plaintext block and returns a ciphertext block of the same size. However, in many applications, a plaintext (e.g. a text file or an image) is composed of several (maybe in thousands or even more) blocks. When plaintext blocks are repeated in the same data or message and identically encrypted, an attacker may infer some information regarding the ciphertexts that he/she intercepted. In addition, in many applications, the recipient of a message may need to authenticate the message sender. Chapter 8 addresses standard operation modes of block ciphers to guarantee confidentiality. The NIST recommends 11 modes (ECB, CBC, CBC-S1, CBC-S2, CBC-S3, OCB, CTR, CFB, FF1, FF-3, and XTS-AES) for guaranteeing confidentiality. Chapter 9 focuses on modes of operation of block ciphers to provide either authentication or confidentiality and authentication. NIST recommends three modes (CMAC, GMAC, and Poly1305-AES), for authentication-only, and six modes (CCM, GMAC, AED-ChaCha20-Poly1305, KW, KWP, and TKW) for authentication and confidentiality. All the 20 operation modes recommended by NIST are addressed in detail in Chapters 8 and 9. Known attacks against operation modes are also discussed.

Chapter 10: Modern cryptographic security relies on the computational difficulty to break ciphers rather than on the theoretical impossibility to break them. If adversaries have enough resources and time, they can break any cipher. The security analysis of block ciphers and their modes of operation is a wide field in cryptanalysis. It aims at finding bounds on the amount of data to encrypt with the same key without compromising the security of encrypted data. Chapter 10 introduces security analysis in which adversaries are given black boxes that simulate block ciphers or their modes of operation. Then, adversaries query black boxes, receive ciphertexts, plaintexts, or tags, and try to guess some information about the used keys or to forge signatures or message tags. Secure ciphers are those ciphers for which the advantage of adversaries is negligible if their resources and time remain below some limits. The analysis of different scenarios of attacks is an approach to assess the security of ciphers from a probabilistic point of view.

Chapter 11: Cryptanalysis is the science and techniques of analyzing and breaking cryptographic algorithms and protocols. It is a very exciting and challenging field. There exist hundreds of cryptanalysis attack variants. Chapter 11 aims at presenting the most known cryptanalysis attacks against symmetric ciphers, namely memory-time trade-off attacks, linear cryptanalysis, differential cryptanalysis algebraic cryptanalysis, cube attacks, divide-and-conquer attacks, and correlation attacks.

Chapter 12: The turning point in modern cryptography occurred in 1976–1977, when Diffie and Hellman on one side and Rivest, Shamir, and Adleman, on the other, proposed original schemes to secure systems without requiring a unique cipher key shared by both parties. The proposed schemes were and are still used to design public-key cryptosystems. The latter provide support to secure communications worldwide between people who do not a priori know each other. The first and still most widely used public-key cryptosystem is with no doubt RSA. Modern cryptography is founded on the idea that the key used to encrypt messages can be made public, while the key used to decrypt messages must be kept private. Chapter 12 aims to describe public-key algorithms and protocols, for providing confidentiality, integrity, and authentication guarantees. They include RSA, Diffie-Hellman key exchange, Menezes-Qu-Vanstone, and ElGamal cryptosystems. The security of public-key cryptosystems is based on either the integer factorization problem or the discrete logarithm problem over cyclic groups. Those problems are known to be computationally infeasible for large numbers; and they are discussed in this chapter. Known attacks against addressed algorithms are introduced.

Chapter 13: The second generation of public-key cryptosystems are based on elliptic curve theory. Elliptic curve (EC) cryptography algorithms entered wide use in 2004. After a slow start, EC-based algorithms are gaining popularity and the pace of adoption is accelerating. EC cryptosystems have been adopted by Amazon, Google, and many others to secure communications with their customers. EC cryptosystems amply outperform RSA-based cryptosystems. Until 2015, the NSA (National Security Agency, US) recommended 256-bit EC cryptography for protecting classified information up to the secret level and 384-bit for Top-secret level. Since 2015, the NSA has recommended 384-bit for all classified information. IETF standards have been proposed to support EC for Transport Layer Security. Chapter 13 aims at addressing different forms of EC-based algorithms, such as ECDSA, to provide confidentiality, integrity, and authenticity guarantees. Compared to RSA, EC-based algorithms make use of more difficult mathematical operations, which are addressed in this chapter.

Chapter 14: Keys are owned and used by entities that interact with each other to perform specific operations in different fields of activities. These keys are analogous to the combination of a safe. If adversaries know the combination of a safe, then the latter does not provide any security against attacks, even it is very complex. Keys are the most valuable items in computer security. Therefore, their protection is of paramount importance. Chapter 14 focuses on key management, which provides functions to secure cryptographic keys throughout their lifetime. It mainly includes key generation, storage, distribution, recovery, suspension, and withdrawal. This chapter aims at introducing the main mechanisms and protocols for key generation, key agreement, key transport, and key distribution over unsecure channels.

Chapter 15: Parties, which exchange encrypted messages over the internet, need to trust each other to secure their operations and transactions in e-commerce, e-banking, e-voting, etc. In addition, parties that exchange messages or access encrypted data inside a company or an institution, where messages/data are encrypted using symmetric keys, need to securely share their keys. Chapter 15 addresses both situations and presents different notions, including key distribution center, digital certificate, certification authority, and Public-key infrastructures (PKIs). PKIs are of paramount importance to establish trust between partners that do not a priori trust each other in the open digital world. Today, digital certificates are used by billions of end-entities, including web servers and their clients, to authenticate each other. The main protocol to secure communications over the internet is with no doubt TLS (Transport Layer Security); it is introduced in this chapter.

Chapter 16: Modern cryptography is fundamentally based on large random and prime numbers. In particular, keys should be generated using large random numbers; and RSA keys are generated using large prime numbers. Any weakness (in term of randomness) in a selected key may result in damage of data and messages protected by that weak key. Chapter 16 addresses algorithms and methods recommended to generate random and prime numbers. True random numbers are hard to produce by computer. In consequence, deterministic random number generators (DRNGs) are of common use in cryptography. However, it is of prime importance to use only DRNGs recommended by NIST and IETF. DRNGs cannot guarantee that generated integers are prime. Therefore, algorithms for testing primality are of common use in cryptography. When prime numbers are required, only provable and probable primes should be used. Probable primes are those integers shown to be prime by probabilistic tests. Both types of primes are discussed in this chapter.

Appendix: A series of 200 multiple choice questions (with answers), relating to computer security in general and to cryptography in particular, are proposed for knowledge testing. These MCQs were collected from various sources, including questions for job applicants, course certification, and exams in IT security field.

Using the Book as a Course

Some chapters are independent of each other, while some chapters are grouped into blocks, because they share notions, objectives, or mathematical background. Chapter blocks are marked with dotted lines. Therefore, the book may be used in different ways, depending on the audience. In particular, chapters focusing on symmetric-key algorithms are independent of those addressing public-key algorithms. Various learning paths are suggested in the figure below, where single arrows show the recommended sequential reading order of chapters, while double arrows indicate that the reader can focus on chapter blocks in any order.

Chapters 1 and 2 are introductive. Therefore, it is recommended to read them. Chapter 3 recalls mathematical background. It could be skipped and, at any time, the reader can return to this chapter to learn about mathematical notions used in the other chapters. For readers not familiar with modular arithmetic and algebra notions, it is recommended to take time to address the exercises given in Chapter 3.

Chapter 4 is a review of historical ciphers. It is recommended in order to learn some roots of modern cryptography. Chapter 5 presents notions relevant to both symmetric and asymmetric cryptosystems.

The two big chapter blocks (i.e. symmetric and asymmetric algorithms, protocols, and standards), may be addressed in any order. However, we recommend finishing a block before starting the other one. Chapters 10 and 11 focus on advanced notions in cryptanalysis of symmetric ciphers. Therefore, they are recommended for graduate students.

For feedback, contact the author at

[email protected] or [email protected]

1 Introduction to Computer Security

Information and computer technologies (ICT), or simply IT technologies, are everywhere, in all fields of activities (business, commerce, transportation systems, health, leisure, education, administration, national security, army, etc.). Nowadays, human beings are more than ever dependent on IT technologies. Therefore, IT security became a paramount concern for any owner or user of electronic devices.

Since the early stage of computers, cyberattacks have never stopped. Worse, statistics provided annually by cybercrime observers and experts often show increases in attacks worldwide. In particular, ransom attacks have become the most lucrative criminal activities in the cyberspace. Partial or total shutdown of systems, as long as ransoms are not paid, results in losses in billions of dollars for companies, hospitals, e-merchants, banks, and individuals.

This chapter aims at providing an introduction to the main issues and notions of security in computer-based systems and tries to answer the following questions:

What are the security issues and requirements?

Why and how do security attacks occur?

How to face security attacks? That is, what are the countermeasures to security attacks?

Security techniques encompass at least two distinct domains:

Technical domain, including hardware and software design to address security;

Organizational domain, including education, staff training, and laws to make involved people aware of IT security.

This book addresses security from a technical point of view only; in particular, it addresses cryptography. However, it should be clear that technology alone is not enough to address security. Imagine that you use a sophisticated alarm system in your home, but the code to access the system is “1234”; or if a teenager in your family does not protect the house alarm code when he/she is at school or at sport club; or even worse, he/she forgets switching on the alarm system when he/she leaves your home. Therefore, organizational issues (including education to security) are of prime importance.

Several books (including [1–9] and journal papers [10, 11]) addressed in detail IT security. This chapter aims only to present the notions of IT security, in particular the security services that can be supported by cryptographic algorithms.

1.1 Introduction

1.1.1 Why Do Attacks Occur?

Since the dawn of time, evil behavior of human beings have emerged: stealing or destroying belongings of others, injuring or even killing others, having interest in details or even disclosing the private life of others, etc.

Different human’s defaults result in misbehaving; they include:

Ego (i.e. Be the best and the center of the world).

Greediness (i.e. Own all or the maximum of things/goods).

Curiosity (i.e. Know private details about the others).

Revenge (i.e. Having been mistreated, seek revenge without going through justice).

Competition (i.e. Be the first in sport, business, science, …).

Beliefs (religion) (i.e. Having some religious beliefs, do not agree with those of others or worse hate and fight them).

Opinions (politics, ideology) (i.e. same reasons as those for religious beliefs).

Therefore, there is no unique profile (or reason) for potential attackers and criminals to act. Attacks on computer-based systems are one of the evil facets of humanity. We would say, times change, but the original flaws remain. Attacks can be prevented, detected, and handled to mitigate their effects. We cannot ignore them or naïvely hope that they will definitely cease. From ICT point of view, attacks may be classified as:

Theft of private or confidential data.