What is a commit number?

What is a hash?¶

a hash is:

• a fixed size value that can be used to represent data of arbitrary sizes

• the output of a hashing function

• often fixed to a hash table

Common examples of hashing are lookup tables and encryption with a cyrptographic hash.

A hashing function could be really simple, to read off a hash table, or it can be more complex.

For example:

If we want to represent the status of a program running it has two possible outcomes: success or failure. We can use the following hash table and a function that takes in the content and returns the corresponding hash. Then we could pass around the 0 and 1 as a single bit of information that corresponds to the outcomes.

This lookup table hash works here.

In a more complex scenario, imagine trying to hash all of the new terms you learn in class.

A table would be hard for this, because until you have seen them all, you do not know how many there will be. A more effective way to hash this, is to derive a hashing function that is a general strategy.

A cyrptographic hash is additionally:

• unique

• not reversible

• similar inputs hash to very different values so they appear uncorrelated

Now lets go through each of these properties

Cryptographic Hashes are unique¶

This means that two different values we put in should give different results.

For this property alone, a simple function could work:

def basic_unique(input):
    return input

but this is not a hash because its length would not be constant and not a cryptographic has because it is easily reversible.

Cryptographic Hashes are not reversible¶

This means that given the hash (output), we cannot compute the message(input).

Any function that gives the same output for two (or more) values meets this criteria.

for example modulus:

13%3

10%3

It can be any function that gives the same output for two (or more) values.

but this is not a cryptographic hash

Similar inputs lead to seemingly uncorrelated outpus¶

We can see this using git:

echo "its nice out today" | git hash-object --stdin

6655c41cf1b446c557235ecccec1a82b0fbf7d61

and then we change it just a little bit:

echo "it's nice out today" | git hash-object --stdin

cf901d3af466bbd8e561f2ca7abbbcdbb76a8123

and now the hash is completely different

and again:

echo "it's nice out todey" | git hash-object --stdin

0c9a20c8e06520866007d4b18a2e67d9e079d675

also very different

python

Python 3.12.11 | packaged by conda-forge | (main, Jun  4 2025, 14:38:53) [Clang 18.1.8 ] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 13%3
1
>>> 10%3
1
>>> exit()

echo "password" | git hash-object --stdin

f3097ab13082b70f67202aab7dd9d1b35b7ceac2

++{“lesson_part”: “main”}

Hashes are fixed length¶

So, no matter the size of the input, we get back the same length.

This is good for memory allocation reasons.

We could again write a function that only does this simply:

def fixed_len(input):
    '''
    pad or trim 
    '''
    len_target=100
    str_in = str(input)
    if len(str_in)< len_target:
        return str_in.ljust(len_target,'-')
    else:
        return str_in[:len_target]

What are some ways a hash could be used?

How can hashes be used?¶

Hashes can then be used for a lot of purposes:

• message integrity (when sending a message, the unhashed message and its hash are both sent; the message is real if the sent message can be hashed to produce the same has)

• password verification (password selected by the user is hashed and the hash is stored; when attempting to login, the input is hashed and the hashes are compared)

• file or data identifier (eg in git)

Hashing in passwords¶

Passowrds can be encrypted and the encrypted information is stored, then when you submit a candidate password it can compare the hash of the submitted password to the hash that was stored. Since the hashing function is nonreversible, they cannot see the password.

password breach

blog post

Some sites are negligent and store passwords unencrypted, if your browser warns you about such a site, proceed with caution and definitely do not reuse a password you ever use. (you should never reuse passwords, but especially do not if there is a warning)

An attacker who gets one of those databases, cannot actually read the passwords, but they could build a lookup table. For example, “password” is a bad password because it has been hashed in basically every algorithm and then the value of it can be reversed. Choosing an uncommon password makes it less likely that your password exists in a lookup table.

For example, in SHA-1 the hashing algorithm that git uses

echo "password" | git hash-object --stdin

f3097ab13082b70f67202aab7dd9d1b35b7ceac2

Hashing in Git¶

In git we hash both the content directly to store it in the database (.git) directory and the commit information.

Recall, when we were working in our toy repo we created an empty repository and then added content directly, we all got the same hash, but when we used git commit our commits had different hashes because we have different names and made the commits at different seconds. We also saw that two entries were created in the .git directory for the commit.

Git was originally designed to use SHA-1.

Then the SHA-1 collision attack was discovered

Git switched to hardened HSA-1 in response to a collision.

In that case it adjusts the SHA-1 computation to result in a safe hash. This means that it will compute the regular SHA-1 hash for files without a collision attack, but produce a special hash for files with a collision attack, where both files will have a different unpredictable hash. from.

they will change again soon

GitHub uses git, it is not an alternative implementation or a fork, so yes it will switch too. The developers at GitHub an other git hosts are among the most impacted by the change since they write code that directly interacts with git objects.

git uses the SHA hash primarily for uniuqeness, not privacy

It does provide some security assurances, because we can check the content against the hash to make sure it is what it matches.

This is a Secure Hashing Algorithm that is derived from cryptography. Because it is secure, no set of mathematical options can directly decrypt an SHA-1 hash. It is designed so that any possible content that we put in it returns a unique key. It uses a combination of bit level operations on the content to produce the unique values.

This means it can produce 2¹⁶⁰ different hashes. Which makes the probability of a collision very low.

Workign with git hashes¶

Mostly, a shorter version of the commit is sufficient to be unique, so we can use those to refer to commits by just a few characters:

• minimum 4

• must be unique

we’ll see this in our github inclass repo

cd gh-inclass-sp24-brownsarahm/

with git log

git log

by using some options on git log to make it easier to read a set of them

git log --abbrev-commit --pretty=oneline

9f39946 (HEAD) Merge pull request #5 from compsys-progtools/organizing_ac
fca59e8 (tag: v0.1, origin/organizing_ac) add files for organizing
1e2a45f (my_branch_cehckoutb, my_branch) Merge pull request #4 from compsys-progtools/2-create-an-about-file
81c6f18 (origin/2-create-an-about-file, 2-create-an-about-file) create about file close s #2
faef6af start readme, closes #3
98cff65 Initial commit

For most project 7 characters is enough and by default, git will give you 7 digits if you use --abbrev-commit and git will automatically use more if needed.

How are hashes computed?¶

Hashes are computed on the binary representation of the data, most treat that as numbers and then perform mathematical operations.

you can see the psuedocode to SHA-1

we’ll work a small example, Python can convert characters to ints:

ord('s')

and ints to binary

bin(ord('s'))

with some extra at the start, so if we just want the binary string

str(bin(ord('s')))[2:]

We can use this to make a function that performs an xor based hash.

def xor_hash(message,n):
    '''
    a simple hashing algorithm based on xor that can take a message of 
    any length and return a version of it with a specific bit length n
    '''
    bitstring = ''.join([str(bin(ord(c)))[2:] for c in message])

    # zero pad to make it a multiple of n
    extra = len(bitstring)%n
    num_pad = (n-extra)*int(extra >0)
    padded_bitstring = bitstring + num_pad*'0'

    # split into length n chunks
    split_bitstring = [padded_bitstring[i:i+n] for i in range(0, len(padded_bitstring), n)]

    # now make them back to integers so we can xor
    bin_int_strings = [int("0b" + bits,2) for bits in split_bitstring]
    
    # now xor
    out_hash_int = 0
    for n_int in bin_int_strings:
        out_hash_int = out_hash_int^n_int

    # we would need to left zero pad the binary to keep it correct
    bin_str = str(bin(out_hash_int))[2:]
    extra_out = len(bin_str)%n
    num_pad_out = (n-extra_out)*int(extra_out >0)
    padded_out =  num_pad_out*'0' + bin_str
    return padded_out

You can see this visualized on python tutor

We can test that we get something the right length

xor_hash('hello',8)

for different lengths of input

xor_hash('it is almost break',8)

This is a sort of meta function, so we could make simpler, more specific functions for each length or we can use it with different ones to see

xor_hash('it is almost break',13)

This is not cryptographic though because similar inputs have correlated outputs.

How do we get to the alphanumeric hashes we see?¶

Let’s build this up with some review

What is a Number ?¶

a mathematical object used to count, measure and label

What is a number system?¶

While numbers represent quantities that conceptually, exist all over, the numbers themselves are a cultural artifact. For example, we all have a way to represent a single item, but that can look very different.

for example I could express the value of a single item in different ways:

• 1

• I

Hindu Arabic Number system¶

In modern, western cultures, our number system is called the hindu-arabic system, it consists of a set of numerals: 0,1,2,3,4,5,6,7,8,9 and is a place based system with base 10.

Where does the name come from?¶

• invented by Hindu mathematicians in India 600 or earlier

• called “Arabic” numerals in the West because Arab merchants introduced them to Europeans

• slow adoption

Numerals¶

are the visual characters used to represent quantities

Place based¶

We use a place based system. That means that the position or place of the symbol changes its meaning. So 1, 10, and 100 are all different values. This system is also a decimal system, or base 10. So we refer to the places and the ones (10⁰), the tens (10¹), the hundreds(10²), etc for all powers of 10.

Number systems can use different characters, use different strategies for representing larger quantities, or both.

Not all systems are place based, for example Roman numerals.

Roman Numerals¶

is a number system that uses different numerals and is not a place based system

There are symbols for specific values: 1=I, V=5, X=10, L =50, C = 100, D=500, M = 1000.

In this system the subsequent symbols are either added or subtracted, with no (nonidentity) multipliers based on position.

Instead if the symbol to right is the same or smaller, add the two together, if the left symbol is smaller, subtract it from the one on the right.

For example

Comparing Bases¶

Decimal¶

To represent larger numbers than we have digits on we have a base (10) and then.

we have the ones (10⁰) place, tens (10¹) place, hundreds (10²) place etc.

Binary¶

Binary is any base two system, and it can be represented using any two distinct numerals.

Binary number systems have origins in ancient cultures:

• Egypt (fractions) 1200 BC

• China 9th century BC

• India 2nd century BC

In computer science we use binary because mechanical computers began using relays (open/closed) to implement logical (boolean; based on true/false, also binary) operations and then digital computers use on and off in their circuits.

We typically represent binary using the same hindu-arabic symbols that we use for other numbers, but only the 0 and 1(the first two). We also keep it as a place-based number system so the places are the ones(2⁰), twos (2¹), fours (2²), eights (2³), etc for all powers of 2.

so in binary, the number of characters in the word binary is 110.

so 10 in binary is 2 in decimal

Convert $1001$ in binary to decimal

Octal¶

Is base 8.

We use hindu-arabic symbols, 0,1,2,3,4,5,6,7 (the first eight). Then nine is represented as 11.

In computer science, this numbering system was popular in 6 bit and 12 bit computers, but is has origins before that.

Native Americans using the Yuki Language (based in what is now California)used an octal system because they count using the spaces between fingers and speakers of the Pamean languages in Mexico count on knuckles in a closed fist. Europeans debated using decimal vs octal in the 1600-1800s for various reasons because 8 is better for math mostly. It is also found in Chinese texts dating to 1000BC.

Some examples:

• $$10 \rightarrow 1*8^1 + 0*8^0 = 1*8+0*1 = 8$$
• $$401 \rightarrow 4*8^2 + 0*8^1 + 1*8^0 = 4*64 + 1*0 = 257$$

In computer science we use octal a lot because it reduces every 3 bits of a number in binary to a single character. So for a large number, in binary say 101110001100 we can change to 5614 which is easier to read, for a person.

101110001100 $\rightarrow$ 101 110 001 100 $\rightarrow$ 5614

Hexadecimal¶

base 16, commonin CS because its 4 bits. we use 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.

This is commonly used for representing colors

This is how the git hash is 160 bits, or 20 bytes (one byte is 8 bits) but we represent it as 40 characters. 160/4=40.

Some examples:

Prepare for Next Class¶

1. Create operators.md and make some notes about what you know about operators. What kinds of operators are you familiar with? Which have you seen in programming? math?

2. Refresh your knowledge of logical operations/ logic gates: and, or, xor, not. For an example reference see the logicemu emulator we will use in class

Badges¶

# transition questions

1. Why make the switch? (in detail, not just *an attack*)
2. What impact will the switch have on how git works?
3. Which developers will have the most work to do because of the switch?

Experience Report Evidence¶

Questions After Today’s Class¶

What other like hashing systems are there?¶

There are many. This is a good topic for an explore badge.

One example is the SHA-256 that git is switching to.

are hashes created from the same plaintext the same hash value for everyone or different?¶

If two different people hash the same content they will get the same hash.

So what kind of numbers do the computer work on?¶

The computer represents them in binary.

Do you decide who become TA’s for your class?¶

Mostly, yes.

Is this even safer than a normal password? Is the hash from the password encryption made differently?¶

It’s probably equivalent to a very long password.

What are other commonly used hashing algorithms, and is there a clean system we have derived for easily making variable hashing systems for secluded systems for added security by obscurity?¶

This is a great topic for an explore badge.

are there any other popular number systems outside the ones we leanred today¶

This is your practice badge for today! so, great question, but it’s on you to look around for some.