This is also a course about how crypto can be used within data science.
It’s likely that you have already used crypto in all of your data science projects, perhaps without explicitly thinking about it.
In this image, the lock icon in the web browser means that my computer has a protected connection to the kaggle.com servers.
At a high level, this means that nobody else on the internet can
(Note though that the kaggle.com servers can see what you are doing on their website. We will see later in the semester how even this can potentially be avoided.)
Using crypto is an essential part of providing security over the Internet, which has always been designed as an open network. There is no physical wire that directly connects your computer with the kaggle.com server. Instead, the data flows through several other computers along the way.
Here is a picture of all of the computer servers connected to the Internet in 1968.
Of course, the Internet is much larger now.
But the design of the Internet has fundamentally remained the same.
“The Internet is just the world passing notes in a classroom.”
– Jon Stewart
Getting the crypto right is essential here.
If the system is vulnerable to decoding or tampering by unauthorized parties, then it can lead to universal, covert breaches of security. Moreover, everyone will have a false sense of security.
If the system is too onerous or slow to use, then people will ignore it and move to other, less secure options.
We will see throughout this course that crypto can be used in many ways besides network transmissions on the Internet.
Still though, this example highlights a general theme of all of our applications:
Crypto is a social science that masquerades as a mathematical science.
Our goal is to use the tools from math, computer science, and data science in order to design systems that help people.
At a high level, cryptographic systems attempt to provide (some or all of) the following three objectives.
These three security objectives are sometimes referred to as the “CIA triad.”
Admittedly, these three objectives are both underspecified (lacking mathematical rigor) and overloaded (the terms have many different sub-meanings).
There are many different flavors of confidentiality, integrity, and availability that cryptography can provide… in fact, far more than we have time to cover in this course.
(Note: BU courses CS 357 and CS 538 also cover different aspects of cryptography and its application in modern digital systems. This course has a partial overlap with them, but we will cover many topics that they don’t and vice-versa. You are welcome to register for those courses as well, but they are not required knowledge.)
Blockchains are a data structure to keep track of transactions. Here is the motivating scenario for this unit:
Let’s think about
Let’s start by exploring how money transfers work in the world of physical banking. Suppose Alice writes a check to Bob. What happens?
If everyone is honest, the money is transferred because a bank performs the bookkeeping task of recording every account and its balance.
Now let’s think about what happens if each party is malicious.
We will do this often throughout the course. Remember that crypto is about getting things done in the presence of an adversary. So, we will develop the skill of `thinking like an adversary,’ in order to design secure cryptosystems.
For this single transaction, Alice doesn’t really care whether Bob is malicious or not. That’s because she isn’t expecting to receive anything of value.
In the other direction: even if Bob trusts the bank (for now), he may be suspicious that Alice is trying to deceive him. He needs to be able to verify the following three properties.
Alice properly signed the check: To accomplish this goal, Bob can verify the signature himself, say by comparing the check against Alice’s identification card.
Alice possesses $1 in her bank account: Bob can ask the bank to verify that Alice’s account balance is sufficient for the check to clear. Note that Bob doesn’t even need to learn Alice’s balance, just whether it is greater than $1 or not.
Alice does not double spend the money by writing a check to someone else at the same time: This is the toughest property to achieve, because neither Bob nor the bank know yet whether Alice has overdrafted her account. They will only discover this later; if so, Alice and Bob can use the bank and the legal system to settle their dispute.
By contrast, the digital world is diverse and international. There is no single entity that everyone in the world trusts, nor is there a single legal system to identify and prosecute thieves and money launderers.
So, if we want a digital system of money, then we need a different approach altogether.
It will take us a few lectures to build up the tools for a digital system of transferring money. First, we need to understand two essential crypto tools: digital signatures and hash functions.
To satisfy the unforgeability goal, Alice must have something that the rest of the world does not. We call this special something a “secret key.”
Informally, a digital signature allows Alice to “lock” her message using her secret key.
To satisfy the correctness goal, there is a corresponding public key that anyone can use to verify whether a message was previously “locked” by Alice.
In more detail, a secret key is a long, random sequence of bytes. One common choice is to pick a key that is \(32\) bytes (or \(32 \times 8 = 256\) bits) in length.
For example, here is a secret key (also known as a private key):
# first install PyCryptoDome with, e.g., "pip install pycryptodome"
from Crypto.PublicKey import ECC
secretKey = ECC.generate(curve='P-256')
print(secretKey.export_key(format='PEM'))-----BEGIN PRIVATE KEY-----
MIGHAgEAMBMGByqGSM49AgEGCCqGSM49AwEHBG0wawIBAQQgrlRl1xBJHmq6JiTC
WDbNMCOdNDFeiACl6Lzs7bkgPoyhRANCAATaMgsPEU5AHSYuIGXW2j8ol9y+VwS7
8UsH/6/1g8+xpbbKjj9T1kaulhYme2hU/gp266xGWDsTrnajhN/CI60x
-----END PRIVATE KEY-----This code example is just for illustrative purposes. Do not export a secret key that you are using for any legitimate purpose! It must remain secret, after all. And definitely do not use this specific key that I just posted on the Internet.
As the name suggests, only Alice knows the secret key; she never shares it with anyone. (Hence my warning above.) Additionally, the key is long enough that it is incredibly unlikely that anyone else in the world will be able to guess it by chance.
As a result, knowing the key identifies Alice, in the sense that if you meet a stranger on the Internet who can has the ability to sign a new message that can be verified with Alice’s public key, then this Internet stranger must be Alice! (…Or someone who has compromised Alice’s computer and stolen her keys.)
To give you a sense of the scale here, let’s imagine that I tried to forge Alice’s key in a brute-force manner, simply by guessing every single 32-byte long string and trying to use it to “lock” the message just as Alice did.
Concretely, suppose I create a for loop that iterates from:
from binascii import hexlify
print(hexlify(32 * b'\x00')) # 32 copies of the byte value 0 (printed in hex)b'0000000000000000000000000000000000000000000000000000000000000000'to this:
The set of possible secret keys is finite – concretely, there are \(2^{256}\) possible options. So, it is theoretically possible to enumerate over all of them.
But it isn’t practically feasible to do so. - Running this for loop on my laptop would require more time than the expected remaining length of the universe. - And simply flipping all of these bits back and forth in RAM would consume approximately the energy of the sun.
Granted, surely there might be more effective ways for an attacker to try to break our digital signature scheme (i.e., to forge a signature) that are smarter than this guess-and-check method. But our hope is that any method of forging signatures is infeasible in practice.
We will discuss next week how to formalize this guarantee, and then discuss a few ways of achieving it.