User talk:Sandy Harris/Sandbox: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Sandy Harris
(re-order, put existing text with mine; next I'll combine them)
m (Text replacement - "traffic analysis" to "traffic analysis")
 
(60 intermediate revisions by 2 users not shown)
Line 1: Line 1:
==Principles of cryptosystems==
==Principles and terms ==


In encryption and decryption, a '''key''' is one or more unique values used by an '''encryption or decryption algorithm'''.  Encryption algorithms take as input a key and '''plaintext''', producing '''ciphertext''' output.  For decryption, the process is reversed to turn ciphertext into plaintext. In a [[secret key]] system, decryption requires the same key as was used for encryption. In a [[public key]] system, the two keys are different.
In encryption and decryption, a '''key''' is one or more unique values used by an '''encryption or decryption algorithm'''.  Encryption algorithms take as input a key and '''plaintext''', producing '''ciphertext''' output.  For decryption, the process is reversed to turn ciphertext into plaintext.


The ciphertext produced by an encryption algorithm should bear no resemblance to the original message. Ideally, it should be indistinguishable from a random string of symbols.
The system should be secure against an attacker who knows all its details except the key; this is known as [[Kerckhoffs' Principle]].


The system should also be secure against an attacker who knows all its details except the key; this is known as [[Kerckhoffs' Principle]].
Methods of defeating cryptosystems have a long history and an extensive literature; see [[cryptanalysis]]. Anyone designing or deploying a cyptosystem must take cryptanalytic results into account.
 
The ciphertext produced by an encryption algorithm should bear no resemblance to the original message. Ideally, it should be indistinguishable from a random string of symbols. Any non-random properties may provide an opening for a skilled cryptanalyst.
 
=== Keying ===
 
Even an excellent safe cannot protect against a thief who knows the combination. Even an excellent cipher cannot protect against an enemy who knows the key.
 
Many cryptographic techniques — [[block cipher]]s, [[stream cipher]]s, [[public key]] encryption, [[digital signature]]s, and [[hashed message authentication code]]s — depend on [[cryptographic key]]s. '''None of these can be secure if the key is not.''' Enemies can sometimes read encrypted messages without breaking the cipher; they use [[Cryptanalysis#Practical_cryptanalysis | practical cryptanalysis]] techniques such as breaking into an office to steal keys.
 
The ''quality'' of the keys is almost as important as their secrecy. '''Keys need to be highly random''', effectively impossible to guess. See [[random number]] for details. A key that an enemy can easily guess, or that he can find with a low-cost search, does not provide much protection. Using strong cryptography with a poor key is like buying good locks then leaving the key under the doormat.
 
In applications which encrypt a large volume of data, '''any cipher must be re-keyed from time to time''' to prevent an enemy from accumulating large amounts of data encrypted with a single key. Such a collection facilitates some attacks — see [[code book attack]], [[linear cryptanalysis]] and [[differential cryptanalysis]] in particular, and [[cryptanalysis]] in general. ''It also makes the payoff for breaking that key very large''. Re-keying also limits the damage if a key is compromised in some other way. Neither block ciphers nor stream ciphers typically include a re-keying mechanism; some higher-level protocol manages that and re-keys the cipher using the normal keying mechanism.
 
In some applications, there are natural breaks where a new key should be used. For example it is natural to use a different key for each new message in a message-oriented protocol such as email, or for each new connection in a connection-oriented protocol such as [[SSH]]. This may be all the re-keying required. Or it may not; what if some users send multi-gigabyte emails or stay logged in for months?
 
In other applications, a mechanism for periodic re-keying is required.  For a [[VPN]] connection between two offices, this would normally be the [[Internet Key Exchange]] protocol. For an embassy, it might be a clerk who changes the key daily and an officer who delivers more keys once a month, flying in with a briefcase handcuffed to his wrist.
 
There are many ways to manage keys, ranging from physical devices and [[smartcard]]s to cryptographic techniques such as [[Diffie-Hellman]]. In some cases, an entire [[public key infrastructure]] may be involved. See [[key management]] for details.
 
=== External attacks ===
 
Any of the techniques of [[espionage]] — bribery, coercion, blackmail, deception ... — may be used to obtain keys; such methods are called [[#cryptanalysis#practical cryptanalysis | practical cryptanalysis]]. In general, these methods work against the people and organisations involved, looking for human weaknesses or poor security procedures. They are beyond our scope here; see [[information security]].
 
For computer-based security systems, host security is a critical prerequisite. '''No system can be secure if the underlying computer is not.''' Even systems generally thought to be secure, such as [[IPsec]] or [[PGP]] are ''trivially'' easy to subvert for an enemy who has already subverted the machine they run on. See [[computer security]].
 
For some systems, host security may be an impossible goal. Consider a [[Digital Rights Management]] system whose design goal is to protect content against the owner of the computer or DVD player it runs on. If that owner has full control over his device then the goal is not achievable.
 
Encrypting messages does not prevent traffic analysis; an enemy may be able to gain useful information from the timing, size, source and destination of traffic, even if he cannot read the contents.
 
=== Side channel attacks ===
 
There are also [[Cryptanalysis#Side_channel_attacks | side channel attacks]].


Methods of defeating cryptosystems have a long history and an extensive literature; see [[cryptanalysis]]. Anyone designing or deploying a cyptosystem must take cryptanalytic results into account.
For example, any electrical device handling fast-changing signals will produce '''electromagnetic radiation'''. An enemy might listen to the radiation from a computer or from crypto hardware. For the defenders, there are standards for limiting such radiation; see [[TEMPEST]] and [[protected distribution system]].
 
'''Timing attacks''' make inferences from the length of time cryptographic operations take. These may be used against devices such as [[smartcard]]s or against systems implemented on computers. Any cryptographic primitive — block cipher, [[stream cipher]], [[public key]] or [[cryptographic hash]] — can be attacked this way. '''Power analysis''' has also been used, in much the same way as timing. The two may be combined.
 
'''Differential fault analysis''' attacks a cipher embedded in a [[smartcard]] or other device. Apply stress (heat, mechanical stress, radiation, ...) to the device until it begins to make errors; with the right stress level, most will be single-bit errors. Comparing correct and erroneous output gives the [[cryptanalysis |cryptanalyst]] a window into cipher internals. This attack is extremely powerful; "we can extract the full DES key from a sealed tamper-resistant DES encryptor by analyzing between 50 and 200 ciphertexts generated from unknown but related plaintexts" [http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1997/CS/CS0910].
 
See [[cryptanalysis]] for details and [[information security]] for defenses.


== Secret key systems ==
== Secret key systems ==
Until the 1970s, all cryptosystems used '''secret key''' or [[symmetric key cryptography]] methods. The sender encrypts with a secret key and the receiver must have an identical copy of that key to decrypt.  
{{main|Symmetric key cryptography}}
Until the 1970s, all (publicly known) cryptosystems used '''secret key''' or [[symmetric key cryptography]] methods. In such a system, there is only one secret key for a message; that key can be used either to encrypt or decrypt the message.  Both the sender and receiver must have the key, and third parties (potential intruders) must be prevented from obtaining the key.  Symmetric key encryption may also be called ''traditional'', ''shared-secret'', ''secret-key'', or ''conventional'' encryption.


Historically, ciphers worked at the level of letters; see [[history of cryptography]] for details. Attacks on them used techniques based largely on linguistic analysis, such as frequency counting; see [[cryptanalysis]].
Historically, [[cipher]]s worked at the level of letters; see [[history of cryptography]] for details. Attacks on them used techniques based largely on linguistic analysis, such as frequency counting; see [[cryptanalysis]]. <!-- This should become a more specific link when there is something better to link to -->


On computers, there are two main types of symmetric encryption algorithm:
On computers, there are two main types of symmetric encryption algorithm:
Line 20: Line 59:
A [[stream cipher]] encrypts a stream of input data by combining it with a [[random number | pseudo-random]] stream of data; the pseudo-random stream is generated under control of the encryption key.
A [[stream cipher]] encrypts a stream of input data by combining it with a [[random number | pseudo-random]] stream of data; the pseudo-random stream is generated under control of the encryption key.


A [[one-time pad]] works much like a stream cipher, but it does not need to generate a pseudo-random stream because its key is a ''truly random stream as long as the message''. This is the only known cipher which is provably secure, but it is impractical for most applications because managing such keys is too difficult.
Another method, usable manually or on a computer, is a [[one-time pad]]. This works much like a stream cipher, but it does not need to generate a pseudo-random stream because its key is a ''truly random stream as long as the message''. This is the only known cipher which is provably secure (provided the key is truly random and no part of it is ever re-used), but it is impractical for most applications because managing such keys is too difficult.
 
=== Key management ===


More generally, [[key management]] is a problem for any secret key system.
More generally, [[key management]] is a problem for any secret key system.
[[Symmetric key cryptography]] requires only one key.  That key can be used either to encrypt or decrypt a message.  Both the sender and receiver must have the key, and third parties (potential intruders) must be prevented from obtaining the key.  Symmetric key encryption may also be called ''traditional'', ''shared-secret'', ''secret-key'', or ''conventional'' encryption.  This was the only kind of two-way encryption publicly known until 1976.<ref name=dh2>{{citation
* It is ''critically'' important to '''protect keys''' from unauthorised access; if an enemy obtains the key, then he or she can read all messages ever sent with that key.
| first1 = Whitfield | last1 = Diffie | first2 = Martin | last2 = Hellman
* It is necessary to '''change keys''' periodically, both to limit the damage if an attacker does get a key and to prevent various [[cryptanalysis|attacks]] which become possible if the enemy can collect a large sample of data encrypted with a single key.
| title = New Directions in Cryptography
* It is necessary to '''communicate keys'''; without a copy of the identical key, the intended receiver cannot decrypt the message.
| journal = IEEE Transactions on Information Theory
Managing all of these simultaneously is an inherently difficult problem.
| volume = IT-22
| url = http://citeseer.ist.psu.edu/rd/86197922%2C340126%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/16749/http:zSzzSzwww.cs.rutgers.eduzSz%7EtdnguyenzSzclasseszSzcs671zSzpresentationszSzArvind-NEWDIRS.pdf/diffie76new.pdf pdf
| date = Nov. 1976}} pages = 644-654</ref>  With this kind of encryption alone, it would not be possible to open up a new secure connection on the internet, because there would be no safe way initially to transmit the shared key to the other end of the connection without intruders being able to intercept it. 
 
One example of a secret-key algorithm is the [[Data Encryption Standard]] (DES). DES uses a 56-bit key which is used to derive 16 48-bit round keys. Neither DES nor the variant, triple DES, are secure against modern attacks (see [[cryptographic strength]] for the reasons).  


One practical consideration for using secret key encryption is where, and how, to safely store the key on the computer so that intruders will not be able to obtain it, if they should gain access to the machine. Simply storing the key unencrypted in a file or database is a poor strategy.  Hard coding it inside a program is also risky because it could be fished out using a decompiler or debugger. A preferable strategy would be to encrypt the private key and store it in a file that is protected by the file system; this way, only authorized users of the system should be able to read the file.  But then, where should one store the key used to encrypt the private key?  It becomes a recursive problem.
One problem is where, and how, to safely store the key. In a manual system, you need a key that is long and hard to guess because keys that are short or guessable provide little security. However, such keys are hard to remember and if the user writes them down, then you have to worry about someone looking over his shoulder, or breaking in and copying the key, or the writing making an impression on the next page of a pad, and so on.


== Public key systems==
On a computer, keys must be protected so that enemies cannot obtain them. Simply storing the key unencrypted in a file or database is a poor strategy. A better method is to encrypt the key and store it in a file that is protected by the file system; this way, only authorized users of the system should be able to read the file. But then, where should one store the key used to encrypt the secret key?  It becomes a recursive problem. Also, what about an attacker that can defeat the file system protection? If the key is stored encrypted but you have a program that decrypts and uses it, can an attacker obtain the key via a memory dump or a debugging tool? If a network is involved, can an attacker get keys by intercepting network packets? Can an attacker put a keystroke logger on the machine; if so, he can get everything you type, possibly including keys or passwords.


The second method is called ''public key'' or [[asymmetric key cryptography]]; in this, keys are created in pairs, such that when one is used to encrypt, the other must be used to decrypt. One key is the ''private key''; this is kept secret from everyone. The other is the ''public key''; this can be published anywhere; on the net, in the phonebook, on business cards.  
Communicating keys is an even harder problem. With secret key encryption alone, it would not be possible to open up a new secure connection on the internet, because there would be no safe way initially to transmit the shared key to the other end of the connection without intruders being able to intercept it. A government or major corporation might send someone with a briefcase handcuffed to his wrist, but for many applications this is impractical.


Practical use of asymmetric cryptography, on any sizable basis, requires a [[public key infrastructure]] (PKI). A public key will normally be embedded in a [[digital certificate]] that is issued by a [[certification authority]]. In the event of compromise of the private key, the certification authority can revoke the key by adding it to a [[certificate revocation list]]. Digital certificates, like passports or other identification documents, usually have expiration dates, and a means of verifying both the validity of the certificate and of the certificate issuer.
Moreover, the problem grows quadratically if there are many users. If <math>N</math> users must all be able to communicate with each other securely, then there are <math>N(N-1)/2</math> possible connections, each of which needs its own key. For large <math>N</math> this becomes quite unmanageable.


''Public key'' exchanges are used to open up secure ''secret key'' channels between strangers across the internet.
Various techniques can be used to address the difficulty. A centralised server, such as the [[Kerberos]] system developed at MIT [http://web.mit.edu/Kerberos/] and used (not without controversy [http://slashdot.org/article.pl?sid=00/05/02/158204]) by all versions of [[Microsoft Windows]] since [[Windows 2000]] [http://technet.microsoft.com/en-us/library/bb742431.aspx] is one method. Other techniques use ''two factor authentication'', combining "something you have" (e.g. your ATM card) with "something you know" (e.g. the PIN).


The development of [[#public key | public key]] techniques, describe in the next section, allows simpler solutions.


In contrast with symmetric encryption, '''asymmetric''' encryption, a user has their computer produce two different keys, related mathematically so that data encrypted with one can only be decrypted with the other. One key is the '''public key''' and can be published. The other is the private key and is kept secret, never leaving the user's computer. It was first proposed, in public, in 1976 by  Whitfield Diffie and Martin Hellman.<ref>{{citation
== Public key systems==
{{main|asymmetric key cryptography}}
'''Public key''' or [[asymmetric key cryptography]] was first proposed, in the open literature, in 1976 by  Whitfield Diffie and Martin Hellman.<ref>{{citation
  | first1 = Whitfield | last1 = Diffie | first2=Martin | lastt2 = Hellman
  | first1 = Whitfield | last1 = Diffie | first2=Martin | lastt2 = Hellman
  | title = Multi-user cryptographic techniques
  | title = Multi-user cryptographic techniques
Line 50: Line 89:
  | volume = 5
  | volume = 5
  | pages = 109-112
  | pages = 109-112
  | date = June 8, 1976}}</ref>.   
  | date = June 8, 1976}}</ref>.  The  historian David Kahn described it as "the most revolutionary new concept in the field since polyalphabetic substitution emerged in the Renaissance" <ref>David Kahn, "Cryptology Goes Public", 58 ''Foreign Affairs]'' 141, 151 (fall 1979), p. 153</ref>. There are two reasons public key cryptography is so important. One is that it solves the key management problem described in the preceding section; the other is that public key techniques are the basis for [[#digital signature | digital signatures]].


A [[public key cryptography]] system is constructed so that calculation of the private key is computationally infeasible from knowledge of the public key, even though they are necessarily related. Instead, both keys are generated secretly, as an interrelated pair<ref>Ralph Merkle was working on similar ideas at the time, and Hellman has suggested that the term used should be Diffie-Hellman-Merkle asymmetric key cryptography.</ref>. The historian David Kahn described public-key cryptography as "the most revolutionary new concept in the field since polyalphabetic substitution emerged in the Renaissance".<ref>David Kahn, "Cryptology Goes Public", 58 ''Foreign Affairs]'' 141, 151 (fall 1979), p. 153.</ref>
In a public key system, keys are created in matched pairs, such that when one of a pair is used to encrypt, the other must be used to decrypt. The system is designed so that calculation of one key from knowledge of the other is computationally infeasible, even though they are necessarily related. Keys are generated secretly, in interrelated pairs. One key from a pair becomes the '''public key''' and can be published. The other is the '''private key''' and is kept secret, never leaving the user's computer.


When used for [[communications security#content confidentiality|content confidentiality]], the ''public key'' is typically used for encryption, while the ''private'' or ''secret key'' is used for decryption. There needs to be a separate public-private pair in each direction of communication. The early asymmetric techniques were vulnerable to some forms of [[cryptanalysis]], until Diffie and Hellman showed that public-key cryptography was practucak by presenting the [[Diffie-Hellman]] key exchange protocol<ref name=dh2 />. In 1978, Ronald Rivest, Adi Shamir, and Len Adleman invented [[Rivest-Shamir-Adleman]] ([[RSA]]), another public-key system<ref name=RSA>{{citation
In many applications, public keys are widely published &mdash; on the net, in the phonebook, on business cards, on key server computers which provide an index of public keys. However, it is also possible to use public key technology while restricting access to public keys; some military systems do this, for example. The point of public keys is not that they must be made public, but that they ''could'' be; the security of the system does not depend on keeping them secret.
 
One big payoff is that two users (traditionally, A and B or [[Alice and Bob]]) need not share a secret key in order to communicate securely. When used for [[communications security#content confidentiality|content confidentiality]], the ''public key'' is typically used for encryption, while the ''private key'' is used for decryption. If Alice has (a trustworthy, verified copy of) Bob's public key, then she can encrypt with that and know that only Bob can read the message since only he has the matching private key. He can reply securely using her public key. '''This solves the key management problem'''. The difficult question of how to communicate secret keys securely does not need to even be asked; the private keys are never communicated and there is no requirement that communication of public keys be done securely.
 
Moreover, key management on a single system becomes much easier. In a system based on secret keys, if Alice communicates with <math>N</math> people, her system must manage <math>N</math> secret keys all of which change periodically, all of which must sometimes be communicated, and each of which must be kept secret from everyone except the one person it is used with. For a public key system, the main concern is managing her own private key; that generally need not change and it is never communicated to anyone.
 
Of course, she must also manage the public keys for her correspondents. In some ways, this is easier; they are already public and need not be kept secret. However, it is absolutely necessary to authenticate each public key. Consider a philandering husband sending passionate messages to his mistress. If the wife creates a public key in the mistress' name and he does not check the key's origins before using it to encrypt messages, he may get himself in deep trouble.
 
Public-key encryption is slower than conventional symmetric encryption so it is common to use public key algorithm for key management but a faster symmetric algorithm for the main data encryption. Such systems are described in more detail below; see [[#hybrid cryptosystems | hybrid cryptosystems]].
 
The other big payoff is that, given a public key cryptosystem, [[#digital signature | digital signatures]] are a straightforward application. The basic principle is that if Alice uses her private key to encrypt some known data then anyone can decrypt with her public key and, if they get the right data, they know (assuming the system is secure and her private key unknown to others) that it was her who did the encryption. In effect, she can use her private key to sign a document. The details are somewhat more complex and are dealt with in a [[#digital signature | later section]].
 
Many different asymmetric techniques have been proposed and some have been shown to be vulnerable to some forms of [[cryptanalysis]];  see the [[public key]] article for details. The most widely used public techniques today are the [[Diffie-Hellman]] key agreement protocol<ref name=dh2 /> and the [[RSA]] ([[Rivest-Shamir-Adleman]]) public-key system<ref name=RSA>{{citation
  | first1 = Ronald L. | last1 = Rivest | first2 = Adi |last2= Shamir | first3 = Len | last3 = Adleman   
  | first1 = Ronald L. | last1 = Rivest | first2 = Adi |last2= Shamir | first3 = Len | last3 = Adleman   
  | url = http://theory.lcs.mit.edu/~rivest/rsapaper.pdf  
  | url = http://theory.lcs.mit.edu/~rivest/rsapaper.pdf  
  | title = A Method for Obtaining Digital Signatures and Public-Key Cryptosystems}}</ref> <ref>Communications of the ACM, Vol. 21 (2), pp.120&ndash;126. 1978</ref> Previously released as an MIT "Technical Memo" in April 1977, and published in Martin Gardner's ''Scientific American'' "Mathematical Recreations" column</ref>. In 1997, it finally became publicly known that asymmetric cryptography had been invented by James H. Ellis at [[GCHQ]], a [[United Kingdom|British]] intelligence organization, in the early 1970s, and that both the Diffie-Hellman and RSA algorithms had been previously developed (by Malcolm J. Williamson and Clifford Cocks, respectively)<ref>[http://www.cesg.gov.uk/publications/media/nsecret/notense.pdf Clifford Cocks. A Note on 'Non-Secret Encryption', CESG Research Report, 20 November 1973].</ref>.
  | title = A Method for Obtaining Digital Signatures and Public-Key Cryptosystems}}</ref>. Techniques based on [[elliptic curve]]s are also used.
 
======Generating session keys======
In 1997, it finally became publicly known that asymmetric cryptography had been invented by James H. Ellis at GCHQ, a [[United Kingdom|British]] intelligence organization, in the early 1970s, and that both the Diffie-Hellman and RSA algorithms had been previously developed (by Malcolm J. Williamson and Clifford Cocks, respectively)<ref>[http://www.cesg.gov.uk/publications/media/nsecret/notense.pdf Clifford Cocks. A Note on 'Non-Secret Encryption', CESG Research Report, 20 November 1973].</ref>.
The primary usage of public-key encryption is in hybrid systems where a symmetric algorithm does the bulk data encryption while the public key algorithm provides other services. Public-key encryption is slower than conventional symmetric encryption.For example, in [[Pretty Good Privacy]] ([[PGP]]) email encryption the sender generates a random key for the symmetric bulk encryption and uses public key techniques to securely deliver it to the receiver. In the [[Diffie-Hellman]] key agreement protocol, used in [[IPsec]] and other systems, public key techniques provide authentication.
 
== Cryptographic hash algorithms ==
{{main| Hash (cryptography)}}
 
'''Hashing''' or '''message digest''' algorithms take an input of arbitrary size and produce a fixed-size digest, a sort of fingerprint of the input document. Some of the techniques are the same as those used in other cryptography but the goal is quite different. Where ciphers (whether symmetric or asymmetric) provide secrecy, hashes provide authentication.
 
Using a hash for [[information security#integrity|data integrity protection]] is straightforward. If Alice hashes the text of a message and appends the hash to the message when she sends it to Bob, then Bob can verify that he got the correct message. He computes a hash from the received message text and compares that to the hash Alice sent. If they compare equal, then he knows (with overwhelming probability, though not with absolute certainty) that the message was received exactly as Alice sent it. Exactly the same method works to ensure that a document extracted from an archive, or a file downloaded from a software distribution site, is as it should be.
 
However, the simple technique above is useless against an adversary who intentionally changes the data. The enemy simply calculates a new hash for his changed version and stores or transmits that instead of the original hash. '''To resist an adversary takes a keyed hash''', a [[hashed message authentication code]] or HMAC. Sender and receiver share a secret key; the sender hashes using both the key and the document data, and the receiver verifies using both. Lacking the key, the enemy cannot alter the document undetected.
 
If Alice uses an HMAC and that verfies correctly, then Bob knows ''both'' that the received data is correct ''and'' that whoever sent it knew the secret key. If the rest of the system is secure, then only Alice knows that key, so he knows Alice was the sender. An HMAC provides [[information security#source authentication|source authentication]] as well as data authentication.
 
==Digital signatures==
{{main| Digital signature}}


An advantage of asymmetric over symmetric cryptosystems is that all symmetric system keys must be kept secret, and the logistics of [[key management]] become complex.  Each distinct pair of communicating parties must share a different key. The number of keys required increases as the square of the number of network members, which requires very complex key management schemes in large networks.  The difficulty of establishing a secret key between two communicating parties when a [[secure channel]] doesn't already exist between them also presents a chicken-and-egg problem which is a considerably practical obstacle for cryptography users in the real world.
Two cryptographic techniques are used together to produce a '''digital signature''', a [[#Cryptographic hash algorithms | hash]] and a [[#Public key systems | public key]] system.


======Digital signatures======
Alice calculates a hash from the message, encrypt that hash with her private key and appends the encrypted hash to the message as a signature. To verify the signature, Bob needs a trustworthy copy of Alice's public key. He uses that to decrypt the signature; this should give him the hash Alice calculated. He then hashes the received message body himself to get another hash value and compares the two hashes.
In addition to encryption, public-key cryptography can be used to implement [[digital signature]] schemes.  A digital signature is somewhat like an ordinary [[signature]]; they have the characteristic that they are easy for a user to produce, but difficult for anyone else to [[forgery|forge]]. Digital signatures can also be permanently tied to the content of the message being signed; they cannot be 'moved' from one document to another, for any attempt will be detectable. In digital signature schemes, there are two algorithms: one for ''signing'', in which a secret key is used to process the message (or a hash of the message or both), and one for ''verification,'' in which the matching public key is used with the message to check the validity of the signature. [[RSA]] and [[Digital Signature Algorithm|DSA]] are two of the most popular digital signature schemes.  Digital signatures are central to the operation of [[public key infrastructure]]s and to many network security schemes ([[Transport Layer Security]] (TLS),<ref name=RFC>{{citation
| id = RFC5246
| title = The Transport Layer Security (TLS) Protocol Version 1.2.
| author = T. Dierks, E. Rescorla
| date = August 2008
| url = http://www.ietf.org/rfc/rfc5246.txt}}</ref> also [[Secure Sockets Layer]] (SSL), many [[VPN]]s, etc).<ref name="schneierbook">{{citation
| first = Bruce | last = Schneier
| title = Applied Cryptography
| date = 2nd edition, 1996,
| publisher = John Wiley & Sons
|ISBN =0-471-11709-9}}</ref>


===One-way encryption===
If the two hash values are identical, then Bob knows with overwhelming probability that the document Alice signed and the document he received are identical. He also knows that whoever generated the signature had Alice's private key. If both the hash and the public key system used are secure, and no-one except the sender knows his private key, then the signatures are trustworthy.
There are a substantial number of applications where it is not necessary to be able to reconstruct the plaintext from the ciphertext, but merely to be able to prove that some piece of information could be generated only from the original plaintext. See [[one-way encryption]] for the techniques; some applications are presented here.
====Protection against record modification====
====Protection against file modification====
====Protecting stored passwords====
When passwords are stored on a computer, it is essential that they be kept secret. Thus it is recommended practice to encrypt the passwords before writing them to disk, and furthermore to prevent anyone who might find them from decrypting them.  ''One-way'' encryption involves storing an encrypted string which cannot be decrypted.  When a user later enters their password, the newly enter password is first encrypted, and then is compared to the encrypted stored string.


The password is usually encrypted as a [[message digest]] or hash, a large number generated by scrambling and condensing plain text letters. An example of a hash digest is SHA-1, which dates from 1994. The SHA-1 algorithm takes a string as input. The algorithm is a digest because the result is a fixed-size number. The SHA-1 algorithm always outputs a 160-bit number (20 bytes of storage). 48 decimal digits would be required to express this number, and it is usually displayed to humans as a 28-character, base-64 encoded string.  Here are some examples:
A digital signature has some of the desirable properties of an ordinary [[signature]]. It is easy for a user to produce, but difficult for anyone else to [[forgery|forge]]. The signature is  permanently tied to the content of the message being signed; it cannot be copied from one document to another, or used with an altered document, since the different document would give a different hash.
 
Any public key technique can provide digital signatures. [[RSA]] is widely used, as is the US government standard [[Digital Signature Algorithm]] (DSA).
 
Once you have digital signatures, a whole range of other applications can be built using them. Many software distributions are signed by the developers; users can check the signatures before installing. Some operating systems will not load a driver unles it has the right signature. On [[Usenet]], things like new group commands and [[NoCeM]]s [http://www.xs4all.nl/~rosalind/nocemreg/nocemreg.html] carry a signature. The digital equivalent of having a document notarised is to get a trusted party to sign a combination document &mdash; the original document, plus at least some identifying information for the notary and a time stamp.
 
[[Digital certificate]]s are the digital analog of an identification document such as a driver's license, passport, or business license. Like those documents, they usually have expiration dates, and a means of verifying both the validity of the certificate and of the certificate issuer. Like those documents, they can sometimes be revoked.
 
Practical use of asymmetric cryptography, on any sizable basis, requires a [[public key infrastructure]] (PKI). In typical PKI's, public key are embedded in [[digital certificate]]s issued by a [[certification authority]]. In the event of compromise of the private key, the certification authority can revoke the key by adding it to a [[certificate revocation list]]. There is often a hierarchy of certificates, for example a school's certificate might be issued by a local school board which certified by the state education department, that by the national education office, and that by the national government master key.
 
An alternative non-hierarchical [[web of trust]] model is used in [[PGP]]. Any key can sign any other; digital certificates are not required. Alice might accept the school's key as valid because her friend Bob is a parent there and has signed the school's key. Or because the principal gave her a business card with his key on it and he has signed the school key. Or both. Or some other combination; Charles has signed Diana's key and she signed the school's. It becomes fairly tricky to decide whether that last one justifies accepting the school key, however.
 
== Hybrid cryptosystems ==
{{main| Hybrid cryptosystem}}
 
Most real applications combine several of the above techniques into a [[hybrid cryptosystem]]. Public-key encryption is slower than conventional symmetric encryption, so use a symmetric algorithm for the bulk data encryption. On the other hand, public key techniques handle the key management problem well, and that is difficult with symmetric encryption alone, so use public key methods for that. Neither symmetric nor public key methods are deal for data authentication; use a hash for that. Many of the protocols also need cryptographic quality [[random number]]s.
 
Examples abound, each using a somewhat different combination of methods to meet its particular application requirements.
 
In [[Pretty Good Privacy]] ([[PGP]]) email encryption the sender generates a random key for the symmetric bulk encryption and uses public key techniques to securely deliver it to the receiver. Hashes are used in generating digital signatures.
 
In [[IPsec]] (Internet Protocol Security) public key techniques provide [[information security#source authentication|source authentication]] for the gateway computers which manage the tunnel. Keys are set up using the [[Diffie-Hellman]] key agreement protocol and the actual data packets are (generally) encrypted with a [[block cipher]] and authenticated with an [[HMAC]].
 
In [[Secure Sockets Layer]] (SSL) or the later version [[Transport Layer Security]] (TLS) which provides secure web browsing (http'''s'''), digital certificates are used for [[information security#source authentication|source authentication]] and connections are generally encrypted with a [[stream cipher]].
 
== One-way encryption ==
{{main|One-way encryption}}
There are applications where it is not necessary to be able to reconstruct the plaintext from the ciphertext, but merely to be able to prove that some piece of information could be generated only from the original plaintext. In some cases, it is undesirable for anyone to be able to reverse the process.
 
A typical example is storing passwords on a computer; they must be kept secret, ideally they would remain secret even if the system administrator was dishonest or if an intruder gained administrator privileges. Thus it is standard practice to encrypt the passwords before writing them to disk, and furthermore to choose an encryption method that does not have a matching decryption so that an intruder or a rogue administrator cannot decrypt the stored forms and obtain passwords. This accomplishes the goal of passwords, providing [[authentication]] of users. When a user enters their password, it can be encrypted, and then compared to the stored encrypted password; if they match, the user got the password right.
 
Early [[Unix]] systems used [[DES]] but used the password as key rather than as plaintext so the algorithm was not reversible. In principle, any [[block cipher]] could be used in a similar way. Modern systems generally use a [[#Cryptographic hash algorithms| hash]] algorithm, which gives a fixed-size digest. Using [[SHA-1]], for example, gives a 160-bit digest (20 bytes of storage). It is usually stored in a human-readable form, a 28-character, base-64 encoded string.  Here are some examples:


  Hello World  z7R8yBtZz0+eqead7UEYzPvVFjw=
  Hello World  z7R8yBtZz0+eqead7UEYzPvVFjw=
Line 91: Line 170:
  Vb            e3PaiF6tMmhPGUfGg1nrfdV3I+I=
  Vb            e3PaiF6tMmhPGUfGg1nrfdV3I+I=
  vB            gzt6my3YIrzJiTiucvqBTgM6LtM=
  vB            gzt6my3YIrzJiTiucvqBTgM6LtM=
Password systems generally also include some ''salt'', extra data added to the password before encryption or hashing. This helps prevent [[dictionary attack]]s. A enemy cannot simply encrypt very word in the dictionary and then search for matches in the password file. If there are 12 bits of salt, then each dictionary word will have 4096 possible matches for different salt values; this makes the attack harder. A side effect is that if a user uses the same password on multiple systems, they will encrypt differently because each system uses different salt. Of course users should still not use dictionary words as passwords or re-use the same password on different systems.
== Steganography ==
{{main|Steganography}}
[[Steganography]] is the study of techniques for hiding a secret message within an apparently innocent message. For example, given an image with 1 M pixel and 3 bytes for different colours in each pixel, one could hide 3 Mbits of message in the least significant bits of each byte, with reasonable hope that the change to the image would be unnoticeable.

Latest revision as of 08:36, 22 June 2024

Principles and terms

In encryption and decryption, a key is one or more unique values used by an encryption or decryption algorithm. Encryption algorithms take as input a key and plaintext, producing ciphertext output. For decryption, the process is reversed to turn ciphertext into plaintext.

The system should be secure against an attacker who knows all its details except the key; this is known as Kerckhoffs' Principle.

Methods of defeating cryptosystems have a long history and an extensive literature; see cryptanalysis. Anyone designing or deploying a cyptosystem must take cryptanalytic results into account.

The ciphertext produced by an encryption algorithm should bear no resemblance to the original message. Ideally, it should be indistinguishable from a random string of symbols. Any non-random properties may provide an opening for a skilled cryptanalyst.

Keying

Even an excellent safe cannot protect against a thief who knows the combination. Even an excellent cipher cannot protect against an enemy who knows the key.

Many cryptographic techniques — block ciphers, stream ciphers, public key encryption, digital signatures, and hashed message authentication codes — depend on cryptographic keys. None of these can be secure if the key is not. Enemies can sometimes read encrypted messages without breaking the cipher; they use practical cryptanalysis techniques such as breaking into an office to steal keys.

The quality of the keys is almost as important as their secrecy. Keys need to be highly random, effectively impossible to guess. See random number for details. A key that an enemy can easily guess, or that he can find with a low-cost search, does not provide much protection. Using strong cryptography with a poor key is like buying good locks then leaving the key under the doormat.

In applications which encrypt a large volume of data, any cipher must be re-keyed from time to time to prevent an enemy from accumulating large amounts of data encrypted with a single key. Such a collection facilitates some attacks — see code book attack, linear cryptanalysis and differential cryptanalysis in particular, and cryptanalysis in general. It also makes the payoff for breaking that key very large. Re-keying also limits the damage if a key is compromised in some other way. Neither block ciphers nor stream ciphers typically include a re-keying mechanism; some higher-level protocol manages that and re-keys the cipher using the normal keying mechanism.

In some applications, there are natural breaks where a new key should be used. For example it is natural to use a different key for each new message in a message-oriented protocol such as email, or for each new connection in a connection-oriented protocol such as SSH. This may be all the re-keying required. Or it may not; what if some users send multi-gigabyte emails or stay logged in for months?

In other applications, a mechanism for periodic re-keying is required. For a VPN connection between two offices, this would normally be the Internet Key Exchange protocol. For an embassy, it might be a clerk who changes the key daily and an officer who delivers more keys once a month, flying in with a briefcase handcuffed to his wrist.

There are many ways to manage keys, ranging from physical devices and smartcards to cryptographic techniques such as Diffie-Hellman. In some cases, an entire public key infrastructure may be involved. See key management for details.

External attacks

Any of the techniques of espionage — bribery, coercion, blackmail, deception ... — may be used to obtain keys; such methods are called practical cryptanalysis. In general, these methods work against the people and organisations involved, looking for human weaknesses or poor security procedures. They are beyond our scope here; see information security.

For computer-based security systems, host security is a critical prerequisite. No system can be secure if the underlying computer is not. Even systems generally thought to be secure, such as IPsec or PGP are trivially easy to subvert for an enemy who has already subverted the machine they run on. See computer security.

For some systems, host security may be an impossible goal. Consider a Digital Rights Management system whose design goal is to protect content against the owner of the computer or DVD player it runs on. If that owner has full control over his device then the goal is not achievable.

Encrypting messages does not prevent traffic analysis; an enemy may be able to gain useful information from the timing, size, source and destination of traffic, even if he cannot read the contents.

Side channel attacks

There are also side channel attacks.

For example, any electrical device handling fast-changing signals will produce electromagnetic radiation. An enemy might listen to the radiation from a computer or from crypto hardware. For the defenders, there are standards for limiting such radiation; see TEMPEST and protected distribution system.

Timing attacks make inferences from the length of time cryptographic operations take. These may be used against devices such as smartcards or against systems implemented on computers. Any cryptographic primitive — block cipher, stream cipher, public key or cryptographic hash — can be attacked this way. Power analysis has also been used, in much the same way as timing. The two may be combined.

Differential fault analysis attacks a cipher embedded in a smartcard or other device. Apply stress (heat, mechanical stress, radiation, ...) to the device until it begins to make errors; with the right stress level, most will be single-bit errors. Comparing correct and erroneous output gives the cryptanalyst a window into cipher internals. This attack is extremely powerful; "we can extract the full DES key from a sealed tamper-resistant DES encryptor by analyzing between 50 and 200 ciphertexts generated from unknown but related plaintexts" [1].

See cryptanalysis for details and information security for defenses.

Secret key systems

For more information, see: Symmetric key cryptography.

Until the 1970s, all (publicly known) cryptosystems used secret key or symmetric key cryptography methods. In such a system, there is only one secret key for a message; that key can be used either to encrypt or decrypt the message. Both the sender and receiver must have the key, and third parties (potential intruders) must be prevented from obtaining the key. Symmetric key encryption may also be called traditional, shared-secret, secret-key, or conventional encryption.

Historically, ciphers worked at the level of letters; see history of cryptography for details. Attacks on them used techniques based largely on linguistic analysis, such as frequency counting; see cryptanalysis.

On computers, there are two main types of symmetric encryption algorithm:

A block cipher breaks the data up into fixed-size blocks and encrypt each block under control of the key. Since the message length will rarely be an integer number of blocks, there will usually need to be some form of "padding" to make the final block long enough. The block cipher itself defines how a single block is encrypted; modes of operation specify how these operations are combined to achieve some larger goal.

A stream cipher encrypts a stream of input data by combining it with a pseudo-random stream of data; the pseudo-random stream is generated under control of the encryption key.

Another method, usable manually or on a computer, is a one-time pad. This works much like a stream cipher, but it does not need to generate a pseudo-random stream because its key is a truly random stream as long as the message. This is the only known cipher which is provably secure (provided the key is truly random and no part of it is ever re-used), but it is impractical for most applications because managing such keys is too difficult.

Key management

More generally, key management is a problem for any secret key system.

  • It is critically important to protect keys from unauthorised access; if an enemy obtains the key, then he or she can read all messages ever sent with that key.
  • It is necessary to change keys periodically, both to limit the damage if an attacker does get a key and to prevent various attacks which become possible if the enemy can collect a large sample of data encrypted with a single key.
  • It is necessary to communicate keys; without a copy of the identical key, the intended receiver cannot decrypt the message.

Managing all of these simultaneously is an inherently difficult problem.

One problem is where, and how, to safely store the key. In a manual system, you need a key that is long and hard to guess because keys that are short or guessable provide little security. However, such keys are hard to remember and if the user writes them down, then you have to worry about someone looking over his shoulder, or breaking in and copying the key, or the writing making an impression on the next page of a pad, and so on.

On a computer, keys must be protected so that enemies cannot obtain them. Simply storing the key unencrypted in a file or database is a poor strategy. A better method is to encrypt the key and store it in a file that is protected by the file system; this way, only authorized users of the system should be able to read the file. But then, where should one store the key used to encrypt the secret key? It becomes a recursive problem. Also, what about an attacker that can defeat the file system protection? If the key is stored encrypted but you have a program that decrypts and uses it, can an attacker obtain the key via a memory dump or a debugging tool? If a network is involved, can an attacker get keys by intercepting network packets? Can an attacker put a keystroke logger on the machine; if so, he can get everything you type, possibly including keys or passwords.

Communicating keys is an even harder problem. With secret key encryption alone, it would not be possible to open up a new secure connection on the internet, because there would be no safe way initially to transmit the shared key to the other end of the connection without intruders being able to intercept it. A government or major corporation might send someone with a briefcase handcuffed to his wrist, but for many applications this is impractical.

Moreover, the problem grows quadratically if there are many users. If users must all be able to communicate with each other securely, then there are possible connections, each of which needs its own key. For large this becomes quite unmanageable.

Various techniques can be used to address the difficulty. A centralised server, such as the Kerberos system developed at MIT [2] and used (not without controversy [3]) by all versions of Microsoft Windows since Windows 2000 [4] is one method. Other techniques use two factor authentication, combining "something you have" (e.g. your ATM card) with "something you know" (e.g. the PIN).

The development of public key techniques, describe in the next section, allows simpler solutions.

Public key systems

For more information, see: asymmetric key cryptography.

Public key or asymmetric key cryptography was first proposed, in the open literature, in 1976 by Whitfield Diffie and Martin Hellman.[1]. The historian David Kahn described it as "the most revolutionary new concept in the field since polyalphabetic substitution emerged in the Renaissance" [2]. There are two reasons public key cryptography is so important. One is that it solves the key management problem described in the preceding section; the other is that public key techniques are the basis for digital signatures.

In a public key system, keys are created in matched pairs, such that when one of a pair is used to encrypt, the other must be used to decrypt. The system is designed so that calculation of one key from knowledge of the other is computationally infeasible, even though they are necessarily related. Keys are generated secretly, in interrelated pairs. One key from a pair becomes the public key and can be published. The other is the private key and is kept secret, never leaving the user's computer.

In many applications, public keys are widely published — on the net, in the phonebook, on business cards, on key server computers which provide an index of public keys. However, it is also possible to use public key technology while restricting access to public keys; some military systems do this, for example. The point of public keys is not that they must be made public, but that they could be; the security of the system does not depend on keeping them secret.

One big payoff is that two users (traditionally, A and B or Alice and Bob) need not share a secret key in order to communicate securely. When used for content confidentiality, the public key is typically used for encryption, while the private key is used for decryption. If Alice has (a trustworthy, verified copy of) Bob's public key, then she can encrypt with that and know that only Bob can read the message since only he has the matching private key. He can reply securely using her public key. This solves the key management problem. The difficult question of how to communicate secret keys securely does not need to even be asked; the private keys are never communicated and there is no requirement that communication of public keys be done securely.

Moreover, key management on a single system becomes much easier. In a system based on secret keys, if Alice communicates with people, her system must manage secret keys all of which change periodically, all of which must sometimes be communicated, and each of which must be kept secret from everyone except the one person it is used with. For a public key system, the main concern is managing her own private key; that generally need not change and it is never communicated to anyone.

Of course, she must also manage the public keys for her correspondents. In some ways, this is easier; they are already public and need not be kept secret. However, it is absolutely necessary to authenticate each public key. Consider a philandering husband sending passionate messages to his mistress. If the wife creates a public key in the mistress' name and he does not check the key's origins before using it to encrypt messages, he may get himself in deep trouble.

Public-key encryption is slower than conventional symmetric encryption so it is common to use public key algorithm for key management but a faster symmetric algorithm for the main data encryption. Such systems are described in more detail below; see hybrid cryptosystems.

The other big payoff is that, given a public key cryptosystem, digital signatures are a straightforward application. The basic principle is that if Alice uses her private key to encrypt some known data then anyone can decrypt with her public key and, if they get the right data, they know (assuming the system is secure and her private key unknown to others) that it was her who did the encryption. In effect, she can use her private key to sign a document. The details are somewhat more complex and are dealt with in a later section.

Many different asymmetric techniques have been proposed and some have been shown to be vulnerable to some forms of cryptanalysis; see the public key article for details. The most widely used public techniques today are the Diffie-Hellman key agreement protocol[3] and the RSA (Rivest-Shamir-Adleman) public-key system[4]. Techniques based on elliptic curves are also used.

In 1997, it finally became publicly known that asymmetric cryptography had been invented by James H. Ellis at GCHQ, a British intelligence organization, in the early 1970s, and that both the Diffie-Hellman and RSA algorithms had been previously developed (by Malcolm J. Williamson and Clifford Cocks, respectively)[5].

Cryptographic hash algorithms

For more information, see: Hash (cryptography).


Hashing or message digest algorithms take an input of arbitrary size and produce a fixed-size digest, a sort of fingerprint of the input document. Some of the techniques are the same as those used in other cryptography but the goal is quite different. Where ciphers (whether symmetric or asymmetric) provide secrecy, hashes provide authentication.

Using a hash for data integrity protection is straightforward. If Alice hashes the text of a message and appends the hash to the message when she sends it to Bob, then Bob can verify that he got the correct message. He computes a hash from the received message text and compares that to the hash Alice sent. If they compare equal, then he knows (with overwhelming probability, though not with absolute certainty) that the message was received exactly as Alice sent it. Exactly the same method works to ensure that a document extracted from an archive, or a file downloaded from a software distribution site, is as it should be.

However, the simple technique above is useless against an adversary who intentionally changes the data. The enemy simply calculates a new hash for his changed version and stores or transmits that instead of the original hash. To resist an adversary takes a keyed hash, a hashed message authentication code or HMAC. Sender and receiver share a secret key; the sender hashes using both the key and the document data, and the receiver verifies using both. Lacking the key, the enemy cannot alter the document undetected.

If Alice uses an HMAC and that verfies correctly, then Bob knows both that the received data is correct and that whoever sent it knew the secret key. If the rest of the system is secure, then only Alice knows that key, so he knows Alice was the sender. An HMAC provides source authentication as well as data authentication.

Digital signatures

For more information, see: Digital signature.


Two cryptographic techniques are used together to produce a digital signature, a hash and a public key system.

Alice calculates a hash from the message, encrypt that hash with her private key and appends the encrypted hash to the message as a signature. To verify the signature, Bob needs a trustworthy copy of Alice's public key. He uses that to decrypt the signature; this should give him the hash Alice calculated. He then hashes the received message body himself to get another hash value and compares the two hashes.

If the two hash values are identical, then Bob knows with overwhelming probability that the document Alice signed and the document he received are identical. He also knows that whoever generated the signature had Alice's private key. If both the hash and the public key system used are secure, and no-one except the sender knows his private key, then the signatures are trustworthy.

A digital signature has some of the desirable properties of an ordinary signature. It is easy for a user to produce, but difficult for anyone else to forge. The signature is permanently tied to the content of the message being signed; it cannot be copied from one document to another, or used with an altered document, since the different document would give a different hash.

Any public key technique can provide digital signatures. RSA is widely used, as is the US government standard Digital Signature Algorithm (DSA).

Once you have digital signatures, a whole range of other applications can be built using them. Many software distributions are signed by the developers; users can check the signatures before installing. Some operating systems will not load a driver unles it has the right signature. On Usenet, things like new group commands and NoCeMs [5] carry a signature. The digital equivalent of having a document notarised is to get a trusted party to sign a combination document — the original document, plus at least some identifying information for the notary and a time stamp.

Digital certificates are the digital analog of an identification document such as a driver's license, passport, or business license. Like those documents, they usually have expiration dates, and a means of verifying both the validity of the certificate and of the certificate issuer. Like those documents, they can sometimes be revoked.

Practical use of asymmetric cryptography, on any sizable basis, requires a public key infrastructure (PKI). In typical PKI's, public key are embedded in digital certificates issued by a certification authority. In the event of compromise of the private key, the certification authority can revoke the key by adding it to a certificate revocation list. There is often a hierarchy of certificates, for example a school's certificate might be issued by a local school board which certified by the state education department, that by the national education office, and that by the national government master key.

An alternative non-hierarchical web of trust model is used in PGP. Any key can sign any other; digital certificates are not required. Alice might accept the school's key as valid because her friend Bob is a parent there and has signed the school's key. Or because the principal gave her a business card with his key on it and he has signed the school key. Or both. Or some other combination; Charles has signed Diana's key and she signed the school's. It becomes fairly tricky to decide whether that last one justifies accepting the school key, however.

Hybrid cryptosystems

For more information, see: Hybrid cryptosystem.


Most real applications combine several of the above techniques into a hybrid cryptosystem. Public-key encryption is slower than conventional symmetric encryption, so use a symmetric algorithm for the bulk data encryption. On the other hand, public key techniques handle the key management problem well, and that is difficult with symmetric encryption alone, so use public key methods for that. Neither symmetric nor public key methods are deal for data authentication; use a hash for that. Many of the protocols also need cryptographic quality random numbers.

Examples abound, each using a somewhat different combination of methods to meet its particular application requirements.

In Pretty Good Privacy (PGP) email encryption the sender generates a random key for the symmetric bulk encryption and uses public key techniques to securely deliver it to the receiver. Hashes are used in generating digital signatures.

In IPsec (Internet Protocol Security) public key techniques provide source authentication for the gateway computers which manage the tunnel. Keys are set up using the Diffie-Hellman key agreement protocol and the actual data packets are (generally) encrypted with a block cipher and authenticated with an HMAC.

In Secure Sockets Layer (SSL) or the later version Transport Layer Security (TLS) which provides secure web browsing (https), digital certificates are used for source authentication and connections are generally encrypted with a stream cipher.

One-way encryption

For more information, see: One-way encryption.

There are applications where it is not necessary to be able to reconstruct the plaintext from the ciphertext, but merely to be able to prove that some piece of information could be generated only from the original plaintext. In some cases, it is undesirable for anyone to be able to reverse the process.

A typical example is storing passwords on a computer; they must be kept secret, ideally they would remain secret even if the system administrator was dishonest or if an intruder gained administrator privileges. Thus it is standard practice to encrypt the passwords before writing them to disk, and furthermore to choose an encryption method that does not have a matching decryption so that an intruder or a rogue administrator cannot decrypt the stored forms and obtain passwords. This accomplishes the goal of passwords, providing authentication of users. When a user enters their password, it can be encrypted, and then compared to the stored encrypted password; if they match, the user got the password right.

Early Unix systems used DES but used the password as key rather than as plaintext so the algorithm was not reversible. In principle, any block cipher could be used in a similar way. Modern systems generally use a hash algorithm, which gives a fixed-size digest. Using SHA-1, for example, gives a 160-bit digest (20 bytes of storage). It is usually stored in a human-readable form, a 28-character, base-64 encoded string. Here are some examples:

Hello World   z7R8yBtZz0+eqead7UEYzPvVFjw=
VB            L1SHP0uzuGbMUpT4z0zlAdEzfPE=
vb            eOcnhoZRmuoC/Ed5iRrW7IxlCDw=
Vb            e3PaiF6tMmhPGUfGg1nrfdV3I+I=
vB            gzt6my3YIrzJiTiucvqBTgM6LtM=

Password systems generally also include some salt, extra data added to the password before encryption or hashing. This helps prevent dictionary attacks. A enemy cannot simply encrypt very word in the dictionary and then search for matches in the password file. If there are 12 bits of salt, then each dictionary word will have 4096 possible matches for different salt values; this makes the attack harder. A side effect is that if a user uses the same password on multiple systems, they will encrypt differently because each system uses different salt. Of course users should still not use dictionary words as passwords or re-use the same password on different systems.

Steganography

For more information, see: Steganography.


Steganography is the study of techniques for hiding a secret message within an apparently innocent message. For example, given an image with 1 M pixel and 3 bytes for different colours in each pixel, one could hide 3 Mbits of message in the least significant bits of each byte, with reasonable hope that the change to the image would be unnoticeable.

  1. Diffie, Whitfield (June 8, 1976), "Multi-user cryptographic techniques", AFIPS Proceedings 4 5: 109-112
  2. David Kahn, "Cryptology Goes Public", 58 Foreign Affairs] 141, 151 (fall 1979), p. 153
  3. Cite error: Invalid <ref> tag; no text was provided for refs named dh2
  4. Rivest, Ronald L.; Adi Shamir & Len Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
  5. Clifford Cocks. A Note on 'Non-Secret Encryption', CESG Research Report, 20 November 1973.