Hashes, Starting with MD5 + Blog Update
An Update
It’s been a while since I set this blog up and made my first post, if you can even call an exceptionally brief introduction a post. At last, I am making a new post to talk about something I did recently and to hopefully force myself to write more going forwards. I’ve always wanted a blog to be able to post about technical and non-technical topics and projects I’ve done, but often find that either I don’t actually do (or finish to a standard I consider worth publishing) any projects outside of university and work, or don’t get or make time to write. So while the project I’ve started is still in its infancy, and there’s absolutely no guarantee I will do much more with it (though I do hope to), I am forcing myself to publish this to hopefully get the ball rolling. This comes at a time when I am focusing on personal development and change, which might be a good subject for a future blog post assuming it is successful, but works with what I am trying to achieve here of sharing progress and success more.
I think it is also worth a brief re-introduction, since my position has changed since the last post. I am flaberpengu, a computer science PhD candidate based in the UK. I am interested in mathematics and computer science, and my primary work focus is in zero-knowledge proofs (ZKPs) and other privacy-related technologies and topics in cybersecurity. Outside of work, I enjoy playing video games and watching sports (mainly football and baseball), as well as keeping up with current affairs and news both in and out of the technical world.
Hashes
A topic that has been a recurring interest of mine over the years, yet I’ve never properly dived into, is hash algorithms. Coming from a cybersecurity perspective, they have always been common-place, but I usually treat them as a black box and see them as some kind of mystical algorithm that manipulates bits in a seemingly-random way. However, with their rising prominence in the world of post-quantum cryptography, I began wondering about exactly why they’re secure, or why they’re not in some cases. This is a topic I’m still planning to explore, but in trying to figure this out, I got side-tracked (as ever) and began looking into how they actually work underneath, as I suspect this will aid my understanding of their security. When it comes to algorithms and computer science more broadly, I tend to learn better by doing and by example (and also find programming more interesting that reading theory/papers). So, I have started my repository hashes. Creative naming, I know. The repository can be found here: https://github.com/flaberpengu/hashes
Aims and Goals
The long-term goal of this repository will be for self-teaching purposes - it will be a central location for any hashing (and adjacent) code I write. By keeping it public, it can potentially serve as a useful resource for others if they too want to follow a similar journey to mine. Moreover, the public aspect will hopefully keep me accountable somewhat, and serve as a way to monitor my cryptographic programming skills over time. This code will not be performant or particularly efficient - at least, this is not a focus yet. I do not expect this to be used in any cases other than perhaps prototyping, and indeed advise against this. I do not intend to begin working collaboratively with others on this, as I would like to stress that this is a personal passion project to help teach myself. If you do spot any flaws or issues with my code, though, please feel free to make an issue on Github and/or reach out to me.
The earliest choice I had to make when starting this repository was the choice of programming language. I opted to use Rust. For me, this wasn’t really even something I had to consider. All code I have written while implementing and developing ZKPs has been in Rust, and the ecosystem surrounding cryptography in Rust is extensive and fairly mature by now (by ZKP standards, anyway). Obviously, older projects like OpenSSL opt for either C or C++, but given that I am starting fresh, it made no sense to use languages like those. Without reeling off the regular pro-Rust spiel, it is reassuring that I can eliminate an entire class of bugs without even needing to think about it, particularly handy for a security-sensitive project like this. However, the choice of Rust does still present a learning opportunity for me here - since most hash algorithms operate on bits and bytes directly, I can gain experience with Rust’s approach to this, which is something I’ve not really had to consider when working with other cryptographic code due to higher-level abstractions such as using finite field/elliptic curve libraries that handle all of that anyway. As I eventually look to optimise my code in this repository, I will hopefully gain some knowledge and experience with how to do bit-level stuff in Rust well, and that will then transfer into my other projects.
Another lower-tier aim with this repository is to minimise dependencies. Ideally, my repository will have no external dependencies outside of the default Rust libraries. Not only does this reduce/eliminate opportunities for a supply-chain attack, it also forces me to be less “lazy” in a way, and actually learn to handle parts of the code I’d usually delegate. Since this project is for fun and to learn, I can care less about pure optimisation, whereas for academic/work coding, I would make the inverse sacrifice and use external, “better” libraries rather than rolling my own.
License Choice
By uploading my code publicly, I got to experience the joys of choosing an open-source license for the first time. I’ve put code out to the internet before, but usually either it was small enough or silly enough that I didn’t care what it went out under, or I was bound by other limitations (academic work, dependencies, etc.). I am by no means an expert on open-source licensing or legal matters, but I’d like to think I have at least a basic understanding of what the popular options are and entail, and be able to weigh them up to form my own judgement. This is at least partially due to hours of discussion, and often debate, with one of my friends Misha, who is significantly better read than me in this area. If you’d like their opinions on many of the prevalent licenses, which I disagree with but that is out of scope for this post, check out their software license tier list. I at least partially used their opinions to help form my own, as well as discussions with another friend of mine, Leonardo Bishop, as well as choosealicense.com.
My hashes repository is licensed under the GNU Lesser General Public License v3.0 only (LGPL-3.0-only). For the full license terms, please either check the repository or see the GNU Project’s copy. Briefly, the LGPL is a (weak) copyleft license which allows for distribution and modification of the program’s source code provided it is also distributed under LGPL or GPL and source code is made available. Copyright and license notices must be preserved. Patent rights are expressly granted. Crucially, any larger works that use the program only via interfaces provided by the program may be distributed under different licenses and need not include the source code for the larger work. A few key thoughts and arguments of mine for this choice follow.
I have been of the stance for a long time that while open-source is great and should be what we strive towards, it is unrealistic to expect that proprietary software will never exist - in many cases, it is only logical that it does. Many open source developers are too hard-line and are, in my opinion, blinded by either naivety, optimism, or stubbornness. It is my view that the only practical way for open source software to make large market-share gains long term is to reach a form of compromise with proprietary developers. I see the GPL, and AGPL, as obstacles to this (except in the case where the open-source developer is doing something truly unique and has strong leverage over a proprietary or permissive alternative/competitor) - many proprietary developers will simply avoid any programs that use (A)GPL licenses, and opt for permissive or proprietary options instead. If one wishes to take a principled stand, accept this, and potentially see proprietary alternatives dominate, then that is a fair opinion but not one that I share.
While I discourage use of this project in anything beyond prototype code, I would still like to enable use of my code as a library if someone so wishes to without forcing them to also use the same license as me. For example, if a proprietary program wished to use this library, then they could. In turn, it would lead to increased utilisation of open-source code, which is an obvious positive. However, I still would like any modifications (most notably of interest, any security flaws or bugs, due to the cryptography and security nature of this project) to be upstreamed - if only so I can continue learning and improving my code. Therefore, a permissive license such as MIT or Apache would not suit in this case, since the project would then be relying on goodwill of proprietary developers to share any changes and improvements.
Therefore, it seems a natural fit that this project is released under LGPL-3.0-only. Indeed, if you read the article ‘Why you shouldn’t use the Lesser GPL for your next library’ by the GNU Project, my project and requirements fit their argument of a case where LGPL is appropriate. As for why I opted to use v3.0-only, it is simply because I wish to review the terms of any future versions of the LGPL prior to agreeing to use it. While the GNU Project warns of potential issues for this, many do not apply to me - the lifespan of this code will likely not be long enough to be concerned about far-future copyright, and I intend for this project to be single-author (i.e. me).
AI Usage
Since this is a project simply for my own interest, enjoyment, and education, using AI defeats the point. I am not anti-AI inherently (except for cases involving gen-AI w.r.t. art), and do not agree that AI cannot be used for education purposes. However, the skills I wish to practice in the development of this repository are my cryptographic and lower-level programming skills, my ability to read RFCs and specifications and code against them, and my broad intuition as to why different algorithms are as they are. These skills, in my view, are best developed through curiosity, thinking, and natural exploration.
As to this end, I will not use AI generated code (to the best of my knowledge) in my code. I will attempt to use as few snippets and ideas from online (e.g. forums) as is feasible, though this may change as I move to optimising my implementations. I want to learn to parse these ideas and implementations myself, and understand a spec, working with only input-output test cases and potentially reference code where necessary, though I still aim to not make my code a simple Rust port of existing implementations.
Likewise, my blog post (and others I will write) will not be AI generated. Put bluntly, there is no point - these are my thoughts and opinions, about work I have done, explaining my successes and hardships. Having an AI write this would be completely pointless. I intend to do a longer-form post in future about general thoughts on AI, but that can wait.
MD5
For a starting point, I opted to implement the Message-Digest 5 (MD5) algorithm. This was developed by Ronald Rivest and was first published in April 1992 in RFC 1321. It is the successor to MD4, which was rumoured at the time to have potential security flaws (and has since been found to have major flaws). Since its development, it has been found to be majorly insecure and is deprecated for cryptographic purposes. However, it is still commonly used for integrity checks due to its speed and the simplicity of the algorithm.
I used the RFC spec of MD5 most heavily when working to implement it, avoiding the reference code where possible. I also used the Wikipedia page for MD5 to aid in understanding of the algorithm, including the psuedocode. Overall, this is not a particularly complex algorithm and frankly is something that I’m ashamed to say took longer than it should have. However, much of my difficulty was in handling endianness, especially as I feel the spec is slightly misleading at times. I won’t explain endianness as I would expect any reader of my blog to understand the concept, but at a high-level: I made false assumptions in the early stages as to which endian given values were, and this caused a chain of inconsistencies in my code as I progressed, and made debugging a bit of a pain. Aside from this, most of the code was smooth-sailing, as I’d hope for an algorithm like this. I expect more modern algorithms to be a bit tougher and more time-consuming to implement.
One useful site I used during the development of my code that I would like to list here for future reference is dqydj’s calculator for doing manual bit-wise calculations to sanity check my code.
Short-term future work
I have some immediate short-term plans for this algorithm’s implementation:
- Enable data input from a file, or streamed data input
- Validate the implementation of appending input length (as I found the RFC to be not 100% clear)
- This only matters for inputs with length \(\ge 2^{32}\), so I cannot feasible test it until I have file input implemented
- Optimise use of arrays in place of vectors potentially
- Generally tidy code up
Future plans for hashes
As previously mentioned, the broad goal for this project is to learn how hashing algorithms work more deeply, get an intuition as to why they’re secure, and implement them myself. However, I do have some clearer, more specific plans for my project, which I will split into ‘algorithms’ and ‘usability’.
Algorithms
My next planned algorithm is probably MD6, as it seems sensible to me to look at the successor to the algorithm I have implemented. Similarly, I plan to implement MD4, and potentially also look into why MD4 (and MD5) got broken, to then understand how MD6 tries to combat this.
Beyond this, I would like to implement some of the SHA-family of algorithms, for the obvious reason that they are the other most well-known family of algorithms and are very widely used - seeing how their internals differ would be an interesting exercise.
Then, I would like to investigate and implement some newer algorithms, such as the Blake family (which I see frequently in ZKPs) and Keccak. I would also like to look into some ZK-friendly hash functions, like Poseidon and MiMC. These are fundamentally different in their design and constraints, which I think would introduce some interesting new ideas and concepts both theoretically and programmatically.
Usability
These goals suit a bullet-point list and are not hashing-specific necessarily.
- Create larger suite of tests, compatible with all (or many) algorithms
- Implement benchmarking to get basic set of data points of performance
- Build command-line usage with flags, file input, etc.
- Work out how to make it actually usable as a crate, or nicely as a library at least
- Reduce number of dependencies
- Make algorithms use structs for cleaner method calls
- Make implementation(s) more robust
Conclusion
Overall, this blog post serves as a way to try to motivate myself to write more posts after abandoning the blog for so long, and to introduce my new long-term project. I am aiming to learn a new sub-field in hashing algorithms, and develop my programming skills at the same time.