The Hash Chains and the way an OTP works!
Get your One-Time Password and know-how a bitcoin blockchain work!
The basic meaning of a hash chain is using successive cryptographic hash functions on a piece of data.
x (data) ⟶⟶ [hash function(H)] ⟶⟶ H(x) :single hash function
x ⟶⟶ [H]⟶[H]⟶[H]⟶[H]⟶……. ⟶output: a hash chain
Hn(x):apply H function on x , n times.
It is a one-way function(pre-image resistance for H) i.e., you cannot get x from its hash value.
How OTP(one-time-password) works?
- The server of a service provider generates x, H(x), H²(x), H³(x)……, H^(n+1) (x) using a key.
- In the generation process, the server terminates all the previous input(x) so that nobody can ever access it(smart move and a smarter is yet to come!).
- The user is given n number of passwords: H(x), H²(x), H³(x),…, H^n(x) & the server stores H^(n+1) (x) to authenticate passwords. A notable thing here is that the user uses all the above-given passwords in the reverse order i.e., uses H^n(x) first and then H^(n-1) (x) till H(x).
- Now, a user used its first password( H^n (x) ) and after its usage, the server stores it and it becomes obsolete or useless (the concept of one-time password).
- Next the user will need H^(n-1) (x) and the process can go on till H(x). Now, when the user enters H^(n-1) (x), the server holding all our passwords computes H(H^(n-1) (x)) and verifies with H^n (x). If its a match, the user can log in otherwise not allowed to.
Even if our servers are compromised, all the passwords it stores are now outdated ones. And now the brilliant trick used here by using the password in reverse order i.e., H^n (x) > H^(n-1) (x) > ……… > H²(x) > H(x). This is done so because even if the attacker calculates the hash function, it can know only the right side ones (H^n (x) ) which are outdated passwords! but they cannot the left-side ones due to one-way property of the hash function.
OTPs are used by numerous service providers for authentication purposes in payment services, sign-in purposes, etc. and they have also introduced time constraint for the validity of each password in order to provide minimal time to the attacker so that he can’t break into the password in the meantime using Brute-Force method(224-bit keys used in hash chains takes much more time to be cracked using Brute Force attack-almost infeasible).
As we discussed above that the server provides a set of passwords to the user, so after finishing n number of passwords, the server & user need to go through secure communication again & set up the new set of passwords.
What is the Hash Tree concept?
Also known as Merkel Tree,
Firstly, we would calculate the hash outputs(Hash A, B, C, D)of all the inputs(Transaction A, B, C, D). Then pairs are made out of all the hash outputs and finally, we would get our Merkel Root or Root Hash(H-root), it is dependent on all the nodes. As if we change one input the root hash will be changed. And this also good for security reasons, suppose if the integrity of one node is compromised by an attacker, it will change H-root. Therefore to check if the security is compromised or not, just check the H-root.
Using hash trees, we can locate the point of failure- verification efficiency and it scales exponentially with tree depth.
How bitcoins are using hash chains?
The Bitcoin blockchain is a hash chain of blocks. Each block has a Merkle tree of transactions. During each transaction, the Merkel root(H-root) is appended and hence it is very difficult to break into the blockchains on the basis of previous information.
A hash algorithm turns an arbitrarily-large amount of data into a fixed-length hash as we have discussed in previous blog. The same hash will always result from the same data, but modifying the data by even one bit will completely change the hash(Avalanche effect).
Bitcoin uses the SHA-256 hash algorithm in each block and hence forming blockchains consisting of all of the transactions.
Next, we will be discussing the Message Authentication Code (MAC address) & Digital Signature, how they are being used for the authenticity and integrity of data transferred over a communication channel. Stay tuned!
~Ashutosh
