Leaking password solution

leaking_password.md

A database with user passwords was leaked. The passwords were stored securely using hashing and salting. Specifically, each password was hashed using the SHA-256 algorithm in the following way:

sha256(user_password || SALT)

Here, SALT is a string that is appended to the user password before hashing. Unfortunately, the SALT was also leaked along with the hashed passwords.

Given the following information:

• SALT = "hello-world"
• Hashed password: 5d50d26357d00547ec330d1114904df00866e7153bbe10fdda00dbeda5f50a1d

Your task is to extract the 4-digit integer password that when hashed with the given salt, matches the provided hashed password.

optimized.go

package main

import (
	"bytes"
	"crypto/sha256"
	"encoding/hex"
	"fmt"
	"strconv"
)

func main() {
	result := reverse("5d50d26357d00547ec330d1114904df00866e7153bbe10fdda00dbeda5f50a1d", "hello-world")
	fmt.Println(result)
}



// if there is anything I think this optimized version teaches, is memory management.
func reverse_optimized(hashpassword, salt string) (result int) {
	// Decode target hash once and stops the operation if the hashed password is not 32
	// this helps to speed of the previous algorithm because the given hash password is converted to bytes
	// allowing for direct bytes comparision which is faster that strings comparision
	target, err := hex.DecodeString(hashpassword)
	if err != nil || len(target) != sha256.Size {
		return 0
	}

	
	// create a predefined buffer with a fixed length (because we know the length of the password - 4 digits)
	// this ensures for memory optimizations not always creating a new string per iterations.
	saltBytes := []byte(salt)
	buf := make([]byte, 4+len(saltBytes))
	copy(buf[4:], saltBytes)

	// One thing i can learn from this, is instead iteration from an array, we just iterate from 0..9, we can now
	// improve the algorithm to paralelize it to increase the speed if needed
	for i := 1; i <= 9; i++ {
		for j := 1; j <= 9; j++ {
			for k := 1; k <= 9; k++ {
				for m := 1; m <= 9; m++ {
					// in this place all I am doing is to update the buffer, not creating new strings everytime this
					// loops run, this improves the memory usage 
					buf[0] = byte('0' + i)
					buf[1] = byte('0' + j)
					buf[2] = byte('0' + k)
					buf[3] = byte('0' + m)

					// well I wasn't aware we could just do this. lol its far better than creating a new Sha256 object on
					// every iteration
					sum := sha256.Sum256(buf)
					
					// this is one key optimization because bytes are compared not strings which is a good performance improvement.
					if bytes.Equal(sum[:], target) {
						// Compute numeric value directly instead of during string -> int conversion which is I found out uses reflection 
						// underneath the hood and reflection is popularly known to reduce performance. Reference: https://www.ersin.nz/articles/reflection-is-slow
						return i*1000 + j*100 + k*10 + m
					}
				}
			}
		}
	}
	return 0
}

solution1.go

package main

import (
	"bytes"
	"crypto/sha256"
	"encoding/hex"
	"fmt"
	"strconv"
)

func main() {
	result := reverse("5d50d26357d00547ec330d1114904df00866e7153bbe10fdda00dbeda5f50a1d", "hello-world")
	fmt.Println(result)
}

func reverse(hashpassword, salt string) (result int) {
	set := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}

	for i := 0; i < len(set); i++ { // 0 (1)
		for j := 0; j < len(set); j++ { //  (2)
			for k := 0; k < len(set); k++ {
				for m := 0; m < len(set); m++ {
					fourDigit := fmt.Sprintf("%d%d%d%d", set[i], set[j], set[k], set[m])
					val := fmt.Sprintf("%s%s", fourDigit, salt)

					hasher := sha256.New()
					hasher.Write([]byte(val))
					hashed := hasher.Sum(nil)
					hexForm := fmt.Sprintf("%x", hashed)
					fmt.Printf("equals = %t\n", hexForm == hashpassword)

					if hexForm == hashpassword {
						finalResult, err := strconv.Atoi(fourDigit)
						if err != nil {
							panic(err)
						}
						return finalResult
					}
				}
			}
		}
	}

	return result
}