Tag: Public-key cryptography

So how can a 1.8 million billion billion billion billion billion billion years become a few minutes?

Introduction

I always find it amusing when someone loses a laptop or a USB stick with some sensitive information, and they say “It’s okay, it was encrypted” … which unfortunately, is far from the truth, as the encryption can be easily broken in most cases. But in a previous blog I outlined how it takes 1.8 million billion billion billion billion billion billion years to find a 256 bit encryption key. So how come we can still crack even the strong encryption? Well it tends to be quite easy, as if you have find out where the key is, you can normally open it up, as humans tend to use weak passwords to save their keys. So if prompted to save your newly created password, which would you choose … “$p7GiLl1%69” or “password”? If the answer to this is “password”, then read on … If it isn’t then you are super-human, and easily a match for any intruder.

You’ve got to store it somewhere …

bob10Like it or not, you’ve got to store your encryption key somewhere, as you’ll need it to decrypt your encrypted content. If you loose your key, you’ll not be able to recover your encrypted data. This can become a particular problem when you encrypt your whole disk drive, as you’ll not be able to even start your computer. So how to you keep it secure? Well we could put it in a secret place, but an intruder could search for this. The method that is normally used, it to protect it with a password. So here is the flaw, it takes a 1.8 million billion billion billion billion billion billion years to find the encryption key, but it can take just a few minutes to find out someones password, as the passwords we use are normally memorable, and are thus found with a standard dictionary. So if an intruder pops-off the key with its protection, they can then run it against a standard dictionary, and crack the key. So protecting keys with a simple password, it a bit like having a high quality security systems, and leaving the key to it under the plant pot.

It’s on a certificate

The place to find encryption keys is normally the certificate store, and the important one to find is the digital certificate which contains the private key. Thus even if we use top quality encryption, the certificate itself can be cracked with a dictionary attack. In this video I show how we can break a certificate with a password:

If you want to try my certificate cracker, it is here:

http://buchananweb.co.uk/clienttoolkit.zip

and I’ve created an example of reading a digital certificate with a password:

http://www.asecuritysite.com/Encryption/digitalcert2

where the first certificate has a password of apples and the second as battery. Both are easy to guess from a standard dictionary. With the advent of cloud-based systems, the concept of distributing the cracking over a range of processors becomes so much easier. So to crack an encryption key with purely brute force … almost impossible! … to determine it from a container which is protected by a password … simple … to determine the a source which is based on a phase phrase … just as simple! I often to surveys of audience at conferences, and you would be amazed how many people say they use the name of their pet, or their favorite football team, or the name of someone in their family, all of which are normally easy to guess.

Conclusions

Well we’ve just seen that it’s passwords that’s the problem. Is your password secure from a dictionary attack? Well most people use a fairly simple password, so that they can remember it. So forget about the size of your keys, and the methods used, it is likely that it is the certificate that causes the problems. In fact, it may be the Windows password that will compromise the whole system.

What takes 1.8 million billion billion billion billion billion billion years to find?

Question

4-bit key
4-bit key

So what takes 1.8 million billion billion billion billion billion billion years, on average, to find, and is only 256 things long? Well it is the time it would take you, or to be more precise, your high-powered computer, to find the key used in a 256-bit encryption process. This calculation takes into account that you would be using one of the best computers around, which would be able to process at 1,000,000,000 keys per second, which is much faster most normal desktop computer. The following tables shows you how long it would take for different key sizes:

http://www.asecuritysite.com/encryption/keys

So you can’t understand why it would take so long? Well the number of keys that we have relates to the number of bits that we have in the key. So a 4-bit key would have 8 different keys from 0000 to 1111. An 8-bit key has 256 keys, a 20-bit key has over 1 million keys, and so on. Mostly we start with something like a 56-bit key, which gives us:

72,057,594,037,927,936

different keys. So if we use a computer which checks 1 billion keys per second, then the time to check one key will be 1ns, so the time to find, on average, the key will be:

T = 72,057,594,037,927,936 * 1×10^-9 / 2

which is 36,028,797 seconds, or 600,479 minutes, or 10,007 hours or 416 days, or 1.14 years. But why do we go from just over a year to billions of years? Well for ever bit that we add, we double the key space. So 57 bits takes 2.28 years, 58 bits takes 4.56 years, and so on. Thus it doesn’t take too long to get to a point where it takes billions of years. So for 256-bits, we get:

115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936

different keys, so if you do the calculation you get:

1,835,871,531,540,400,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 years

which is a LONG TIME!

Conclusion

For a completely random key, 256-bits is completely uncrackable with today’s, tomorrow’s computers. If we were to do it, we would need a quantum computer, which could parallelise the computation, and perform them at the speed of light. But the thing we must ask is … are the keys actually random? If not, then it’s a whole different calculation?

The strength is in the keys

Introduction

The main objective of cryptography is to provide a mechanism for two (or more) entities to communicate without any other entity being able to read or change the message. Along with this it can provide other services, such as:

  • Integrity check. This  makes sure that the message has not been tampered with by non-legitimate sources.
  • Providing authentication. This verifies the sender identity. Unfortunately most of the current Internet infrastructure has been build on a fairly open system, where users and devices can be easily spoofed, thus authentication is now a major factor in verifying users and devices.
Key-based encryption
Figure 1: Key-based encryption

One of the main problems with using a secret algorithm for encryption is that it is difficult to determine if Eve has found-out the algorithm used, thus most encryption methods use a key-based approach where an electronic key is applied to a well-known algorithm. Another problem with using different algorithms for the encryption is that it is often difficult to keep devising new algorithms and also to tell the receiving party that the text is being encrypted with the new algorithm. Thus, using electronic keys, there are no problems with everyone having the encryption/decryption algorithm, because without the key it should be computationally difficult to decrypt the message (Figure 1).

The three main methods of encryption are (Figure 2):

  • Encryption methods
    Figure 2: Encryption methods

    Symmetric key-based encryption. This involves the same key being applied to the encrypted data, in order that the original data is recovered. Typical methods are DES, 3DES, RC2, RC4, AES, and so on.

  • Asymmetric key-based encryption. This involves using a different key to decrypt the encrypted data, in order that the original data is recovered. A typical method is RSA, DSA and El Gamal.
  • One-way hash functions. With this it is not possible to recover the original source information, but the mapping between the value and the hashed value is known. The one-way hash function is typically used in authentication applications, such as generating a hash value for a message. The two main methods are MD5 and SHA-1, and it is also used in password hashing applications, where a password is hashed with a one-way function, and the result is stored. This is the case in Windows and UNIX login, where the password is stored as a hash value. Unfortunately, if the password is not a strong one, the hash value is often prone to a dictionary-type attack, where an intruder tries many different passwords and hashes them, and then compares it with the stored one.

Generate your own keys

In order for you to see what keys look like, I’ve created a Web page where you can generate your own keys:

http://asecuritysite.com/Encryption/keygen

For example, we I use “fred” as the pass phrase and for aes-128-cbc (128-bit AES with CBC – Chained Block Cipher), I get:

salt=187938EEE4E87FDA
key=39E2095E5789CAD5CD1995219B48FFE6
iv =6D55F343E0D60985564D2D51D44C40D0

but when I try it again I get:

salt=BEAF690035812A3D
key=610C6519F47ECDDC370B88AECC0A4BDC
iv =247BF2166C1672CA935829B75F814EA4

In this way the salt, the key and the IV value all change, so that they cannot be easily guessed. The salt value allows us to create a difficult to crack hash value, and the IV value allows for the ciphertext to change with the same message. The trick is to add randomness into the generation, so that Eve cannot guess what the generated values are.

Obviously the size of the key will vary with the number of bits in the key, so if we use AES-256 CBC we get:

salt=3142A388014686CA
key=B4E2195C7F2BF04EB67722DF7FB8D5E6B4FE62E9CA9C896760D4435175A4EBA7
iv =8CE70C8998BB237997BFA9ED4B75A587

which shows that the encryption key is twice as long (but the salt and the IV values stay the same).

I’ll cover computational difficulty in the next article….

For the Love of Cryptography

Bob, Alice and Eve

Encoding
Fig 1:Encoding

Computer Security is subject a great subject to study, especially that the area is ever changing, and basically involves the understanding of virtually everything to do with computing … including networks, software, embedded systems, people, crime, and so much more. The thing I love most is cryptography, especially that it is the continual battle between man and computer. A computers get more powerful by the day, and the cloud can distribute both the storage of information and also the processing, it gets more challenging for humans to keep anything secret from them. They thus can determine where we have been, what we have been watching, what we like to have for lunch, and what type of coffee we like, so it’s nice to know that we can still be them at cryptography. Well, we don’t actually beat them, we just make it so difficult, that eventually the humans controlling them will give up. In past times, as you can see from Figure 1, we could code our messages in a way that only Bob and Alice knew the secret code. Unfortunately there was no way of knowing that Eve had actually discovered the code. So humans have had to derive task which are so simple when you know a secret, but extremely difficult if you do not know it.

Big Numbers and Primes

Lots of Key and Primes
Fig 2: Lots of Key and Primes

When I first started in computing computers could only deal with 8 bits at a time – known as the 8-bit processors, such as the Intel 8008. Microprocessor technology then evolved through 16-bit processors (such as with the Intel 8086) and onto 32-bit ones (Intel 80386), and finally to 64-bit processors. Our current hardware architecture for most PCs and mobile devices runs on a 64-bit processor, even though much of the software still runs in a 32-bit mode. Thus most computers are optimized to run with values that are 64-bits long. So one of the ways to make life difficult for computers is to force them to deal with numbers that are much longer than this, such as for 256 bits (for private-key encryption) or 1,024 bit (for public-key encryption). These sizes of numbers make even the addition of two numbers a challenge task, taking many ticks of the clock. For a normal add operation the computer could, with two 64-bit numbers, do it in a fraction of a nano-second, whereas with 1,024 bits it becomes a major task to split the numbers up into chunks, and then perform the addition on the chunks, and with associated carry-over taken into account.

So we end up with the concept of Big Integers in cryptography. These are whole numbers who can be any size we want, and we can undertake some basic operations such as raising to a power, taking the modulus, adding, and so on.

So what does a Big Integer look like? Well for 512-bits we get numbers such as [Example]:

16,051,676,583,321,910,517,842,912,514,242,120,458,388,544,526,515,804,467,341,482,346,
206,707,182,147,774,421,857,300,872,391,674,336,841,094,767,996,574,497,015,038,851,049,
971,545,273,239,933,642,180,743,111,921,076,030,627,772,076,959,051,769,002,395,221,544,
838,304,706,428,767,230,398,563,872,098,020,125,093,711,002,252,870,755,574,445,367,073,
595,571,270,521,653,567,709,801,758,861,271,551,464,325,540

and the challenge for a computer is actually to determine the two prime numbers that when multiplied together actually provides this value. If you’re interested, in this case, they are:

8,044,675,477,712,008,752,023,823,019,578,452,312,930,831,161,771,900,648,214,214,337,291,
200,072,984,849,707,468,990,717,567,849,714,452,612,612,027,658,352,992,397,524,927,866,
652,768,863,179,707,737,287

and:

1,995,316,856,198,054,868,182,625,824,794,282,420,425,397,624,446,426,871,607,556,212,261,
659,943,148,990,748,085,163,805,134,774,302,595,456,418,515,934,616,814,703,707,291,062,
474,935,597,665,671,744,391

This might not seem a difficult task, as surely computers know all the prime numbers possible? Well the answer is no, it takes a great deal of computing power to determine if a number if prime, and we haven’t found them all yet. So normally what we do when we are selecting one is we pick a number, and test if it is prime, if not, take one away, and re-test, and so on, and eventually we will find one. For 1 to 100, here’s the list of primes:

2      3     5     7    11    13
17    19    23    29    31    37
41    43    47    53    59    61
67    71    73    79    83    89
91    97   101   103   107   109

A sample page to determine the prime numbers is here, and to test is here.

Lots of Keys

Key-based Encryption
Key-based Encryption

In standard key-based encryption, we can have a single key, which is secret between Bob and Alice, and then Bob will use it to encrypt his plaintext, and then Alice will use the same key to decrypt. If Bob and Alice know the key, it will be easy for them to encrypt and decrypt, but will be difficult for Eve, and she would have to search for all the possible keys. Thus the other thing we can do to defeat computers is to have lots of different keys – the more the better. Just like when you come home, and you’ve got lots of keys on your key ring, it can take a while to find the right key, the same happens for brute force cracking of encryption. For this the more bits that we have in a key, the more keys that will be possible. So it we had a four bit key, we could have 16 (2 to the power of 4) different keys: 0000, 0001, … 1110 and 1111). In this way we can calculate the key space, and where the average number of keys tried will be half the key space size (as you may be lucky at get it first time, or you may have to search to the end, but, on average, it will take half the key space size).

So we have a lot of keys, but we know that computers are actually very powerful in doing repetitive tasks, so lets determine how long it would take a standard computer to crack some codes which has a certain key size. Let’s start with 32 bits, which gives 4,294,967,296 keys. If we assume that it will take 1 nano seconds to try each key it will take:

T = 4,294,967,296 x 1 x 10^-9 /2 = 2.15 seconds

So it only takes 2 seconds to crack. Let’s try 56 bits (which is the basis of the DES encryption method). Now we have 72,057,594,037,927,936 keys and it will take 1.14 years to crack, on average. For 64-bits we have 18,446,744,073,709,551,616 keys and it will now take 292.47 years, on average, which should be enough to keep more messages secret.

But what about parallel processing and improving computing power? Check back for the next part of this discussion for more details on this.

If you are interested?

If you are interested in anything related to this subject, I’ve created a new presentation at:

The Nightmare that is PKI and Digital Certificates

Introduction

Identity Verification
Identity Verification

Digital certificates support three main functions. The first is to provide a container for your public and your private key. If you want to purchase a digital certificate, the issuer will send you a digital certificate with both the public and the private key on it. So what do we do with this? Well if we have encrypted some data with the private key, we must send the recipient our public key, so the second usage is to strip-off the public key and add it to a digital certificate which is sent to the recipient, who can use it to decrypt the encrypted message. The third usage is related, but has a different function. For this the digital certificate is used to identity an object, such as the sender of a message. In this way the sender signs something in the message with their private key, and then distributes the public key with the certificate, and the recipient gets the signature and can verify the send.

Certificate store
Certificate store

It can be quite cumbersome to send the digital certificate each time we want to prove our identity or to decrypt some encrypted data, so we normally store our certificate in a repository, so that it can be used again (otherwise we can add keys to a key ring). This is either on the local machine, or can be stored on a trusted certificate repository. The screen shot on the right-hand side shows an example of my certificates, where I have stored the certificates for login.live, login.oracle, and so on. Once I accept these certificates, they are then trusted on subsequent visits. It is thus important that users check these certificates when they are first accessed, so that they are checked for their credibility. Unfortunately most users do not check them, and can end-up with certificates which a malicious or, at least, do not provide the right level of verification. For high-risk accesses, such as to your bank or for e-commerce applications, you need to be sure that the certificate has credibility with you.

As we will find the key elements of a digital certificate are: the issuer, the serial number, the date when it is valid from and to, and the public and private keys. If you trust the issuer to make checks on the entity, then you can trust the certificate which has been signed by them. An understanding of who can issue certificates, and the checks that they make is thus important. I sign many PDFs for student references with a self-signed digital certificate … which has absolutely no credibility at all … but the little padlock at the bottom of the PDF looks good though. Basically I have signed it myself, to say that I am me, but anyone else can do the same.

So what about Bob and Alice (and Eve)?

It is possible for Bob to sign a message with his private key, and that this is then decrypted by Alice with her public key? There are many ways that Alice could get Bob’s public key, but a major worry for her is that who does she trust to receive his public key? One way would be for Bob to post his public key on his web site, but what happens if the web site is down, or if it is a fake web site that Alice uses. Also if Alice asked Bob for his public key by email, how does she really know that Bob is the one who is responding? Thus we need a method to pass public keys, in the verifiable way. One of the best ways is to provide a digital certificate which contains, amongst other things, the public key of the entity which is being authenticated. Obviously anyone could generate one of these certificates, so there are two ways we can create trust. One is to setup a server on our own network which provides the digital certificates for the users and devices within an organization, or we could generate the digital certificate from a trusted source, such as from well-known Certificate Authorities (CAs), such as Verisign, GlobalSign Root, Entrust and Microsoft. These are generated by trusted parties and which has their own electronic thumbprint to verify the creator, and thus can be trusted by the recipient, or not. If you want to understand how digital certificates are created, I setup a link for you to create your own certificate:

http://www.asecuritysite.com/encryption/createcert

PKI and Trust

ExampleThe major problem that we now have is how to determine if the certificate we get for Bob is creditable, and can be trusted. The method used for this is to setup a PKI (Public Key Infrastructure), where certificates are generated by a trusted root CA (Certificate Authority), which is trusted by both parties. As seen in Figure 1, Bob asks the root CA for a certificate, for which the CA must check his identity, after which, if validated, they will grant Bob a certificate. This certificate is digitally signed with the private key of the CA, so that the public key of the CA can be used to check the validity of it. In most cases, the CA’s certificate is installed as a default as a Trusted Root Certificate on the machine, and is used to validate all other certificate issued by them. Thus when Bob sends his certificate to Alice, she checks the creditability of it (Figure 2), and if she trusts the CA, she will accept it. Unfortunately, the system is not perfect, and there is a lack of checking of identities from CA, and Eve could thus request a certificate, and be granted one (Figure 3). The other method is to use a self-signed certificate, which has no creditability at all, as anyone can produce a self-signed certificate, as there is no validation of it. An example of this is shown on the right-hand side, where a certificate has been issued to Bill Buchan (even though the user is Bill Buchanan).

cert02Figure 1 Getting a certificate

cert03Figure 2 Alice checks the certificate

cert04Figure 3 Eve spoofs Bob

cert06Thus our trusted root CA, which we will call Trent, is trusted by both Bob and Alice, but at what level of trust? Can we trust the certificate for authenticating emails, or can we trust it for making secure network connections? Also, can we trust it to digital sign software components? It would be too large a job to get every entity signed by Trent (the root authority), so we introduce Bert, who is trusted by Trent to sign on his behalf for certain things, such as that Bert issues the certificate for email signing and nothing else. Thus we get the concept of an intermediate authority, which is trusted to sign certain applications (Figure 4), such as for documentation authentication, code signing, client authentication, user authentication, and so on.

Note that there are typically two digital certificates in use. The one that is created by the CA that has both the private and public key on it (and can be stored on a USB stick, so that the encryption keys can be recovered at any time), and there is one that is distributed which does not have the private key (for obvious reasons).

cert07Figure 4 Trusted root CA, intermediate CA and self-signed

Digital certificate types

Typical digital certificate types are:

  • IKE.
  • PKCS #7.
  • PKCS #10.
  • RSA signatures.
  • X.509v3 certificates. These are exchanged at the start of a conversion to authenticate each device.

A key factor in integrated security is the usage of digital certificates, and are a way of distributing the public key of the entity. The file used is typically in the form of X.509 certificate files. Figure 5 and Figure 6 shows an example export process to a CER file, while Figure 7 shows the actual certificate. The standard output is in a binary format, but a Base-64 conversion can be used as an easy way to export/import on a wide range of systems, such as for the following:

-----BEGIN CERTIFICATE-----
MIID2zCCA4WgAwIBAgIKWHROcQAAAABEujANBgkqhkiG9w0BAQUFADBgMQswCQYD
VQQGEwJHQjERMA8GA1UEChMIQXNjZXJ0aWExJjAkBgNVBAsTHUNsYXNzIDEgQ2Vy
dGlmaWNhdGUgQXV0aG9yaXR5MRYwFAYDVQQDEw1Bc2NlcnRpYSBDQSAxMB4XDTA2
MTIxNzIxMDQ0OVoXDTA3MTIxNzIxMTQ0OVowgZ8xJjAkBgkqhkiG9w0BCQEWF3cu
YnVjaGFuYW5AbmFwaWVyLmFjLnVrMQswCQYDVQQGEwJVSzEQMA4GA1UECBMHTG90
aGlhbjESMBAGA1UEBxMJRWRpbmJ1cmdoMRowGAYDVQQKExFOYXBpZXIgVW5pdmVy
…
H+vXhL9yaOw+Prpzy7ajS4/3xXU8vRANhyU9yU4qDA==
-----END CERTIFICATE-----

The CER file format is useful in importing and exporting single certificates, while other formats such as the Cryptographic Message Syntax Standard – PCKS #7 Certificates (.P7B), and Personal Information Exchange – PKCS #12 (.PFX, .P12) can be used to transfer more than one certificate. The main information for a distributable certificate will thus be:

  • The entity’s public key (Public key).
  • The issuer’s name (Issuer).
  • The serial number (Serial number).
  • Start date of certificate (Valid from).
  • End date of certificate (Valid to).
  • The subject (Subject).
  • CRL Distribution Points (CRL Distribution Points).
  • Authority Information (Authority Information Access). This will be shown when the recipient is prompted to access the certificate, or not.
  • Thumbprint algorithm (Thumbprint algorithm). This might be MD5, SHA1, and so on.
  • Thumbprint (Thumbprint).

The certificate, itself, can then be trusted to verify a host of applications (Figure 4.20), such for:

  • Server authentication.
  • Client authentication.
  • Code signing.
  • Secure email.
  • Time stamping.
  • IP security.
  • Windows hardware driver verification.
  • Windows OEM System component verification.
  • Smart card logon.
  • Document signing.

cert08Figure 5 Exporting digital certificates

cert09Figure 6 Exporting digital certificates

cert10

Figure 7 Digital certificate

cert11Figure 8 Options for signing

So what’s the problem?

Fake or real?
Fake or real?

The theory of creating a public and private key using RSA is sound, and this has proven to be secure (although the number of bits required to keep it secure increases by the day). Unfortunately few people actually know how it works. So, to test you, ask yourself these questions:

  • When was the last time that you checked the credibility of the bank you are visiting?
  • When was the last time you accepted a certificate, even though it had problems?
  • Would you know where to go in a browser to find the details of a certificate, and could you actually interpret them correct?
  • Do you know how your software components on your system are verified for their credibility, and that they can from their original source?
  • Do you know who the most creditably signers of certificates are? Is Google a signer? Is GlobalSign a signer?

If the answer to any of these is “I don’t know”, we have problems the PKI, as it should be there to, unfortunately, protect the end user, but obviously it isn’t.

Unfortunately many people when faced with a certificate will not actually know if the CA is a credible one, or not, and this is the main weakness of the PKI/digital certificate system. There are many cases of self-signed certificate, and of certificates which are not valid, faking the user.

Presentation

There is a demonstration of digital certificates at:

If you’re interesting in methods of authentication, please view: