1109998Smarkm/* 2109998Smarkm * This code is derived from (original license follows): 3109998Smarkm * 4109998Smarkm * This is an OpenSSL-compatible implementation of the RSA Data Security, Inc. 5109998Smarkm * MD5 Message-Digest Algorithm (RFC 1321). 6109998Smarkm * 7109998Smarkm * Homepage: 8109998Smarkm * http://openwall.info/wiki/people/solar/software/public-domain-source-code/md5 9109998Smarkm * 10296341Sdelphij * Author: 11109998Smarkm * Alexander Peslyak, better known as Solar Designer <solar at openwall.com> 12109998Smarkm * 13109998Smarkm * This software was written by Alexander Peslyak in 2001. No copyright is 14109998Smarkm * claimed, and the software is hereby placed in the public domain. 15109998Smarkm * In case this attempt to disclaim copyright and place the software in the 16109998Smarkm * public domain is deemed null and void, then the software is 17109998Smarkm * Copyright (c) 2001 Alexander Peslyak and it is hereby released to the 18109998Smarkm * general public under the following terms: 19109998Smarkm * 20109998Smarkm * Redistribution and use in source and binary forms, with or without 21109998Smarkm * modification, are permitted. 22109998Smarkm * 23109998Smarkm * There's ABSOLUTELY NO WARRANTY, express or implied. 24109998Smarkm * 25109998Smarkm * (This is a heavily cut-down "BSD license".) 26109998Smarkm * 27109998Smarkm * This differs from Colin Plumb's older public domain implementation in that 28109998Smarkm * no exactly 32-bit integer data type is required (any 32-bit or wider 29109998Smarkm * unsigned integer data type will do), there's no compile-time endianness 30109998Smarkm * configuration, and the function prototypes match OpenSSL's. No code from 31109998Smarkm * Colin Plumb's implementation has been reused; this comment merely compares 32109998Smarkm * the properties of the two independent implementations. 33109998Smarkm * 34109998Smarkm * The primary goals of this implementation are portability and ease of use. 35109998Smarkm * It is meant to be fast, but not as fast as possible. Some known 36109998Smarkm * optimizations are not included to reduce source code size and avoid 37109998Smarkm * compile-time configuration. 38109998Smarkm */ 39109998Smarkm 40109998Smarkm#include "llvm/Support/MD5.h" 41109998Smarkm#include "llvm/ADT/ArrayRef.h" 42109998Smarkm#include "llvm/ADT/SmallString.h" 43109998Smarkm#include "llvm/ADT/StringExtras.h" 44109998Smarkm#include "llvm/ADT/StringRef.h" 45109998Smarkm#include "llvm/Support/Endian.h" 46109998Smarkm#include <array> 47109998Smarkm#include <cstdint> 48109998Smarkm#include <cstring> 49109998Smarkm 50109998Smarkm// The basic MD5 functions. 51109998Smarkm 52109998Smarkm// F and G are optimized compared to their RFC 1321 definitions for 53109998Smarkm// architectures that lack an AND-NOT instruction, just like in Colin Plumb's 54109998Smarkm// implementation. 55296341Sdelphij#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) 56296341Sdelphij#define G(x, y, z) ((y) ^ ((z) & ((x) ^ (y)))) 57296341Sdelphij#define H(x, y, z) ((x) ^ (y) ^ (z)) 58296341Sdelphij#define I(x, y, z) ((y) ^ ((x) | ~(z))) 59296341Sdelphij 60109998Smarkm// The MD5 transformation for all four rounds. 61109998Smarkm#define STEP(f, a, b, c, d, x, t, s) \ 62109998Smarkm (a) += f((b), (c), (d)) + (x) + (t); \ 63109998Smarkm (a) = (((a) << (s)) | (((a) & 0xffffffff) >> (32 - (s)))); \ 64296341Sdelphij (a) += (b); 65109998Smarkm 66296341Sdelphij// SET reads 4 input bytes in little-endian byte order and stores them 67296341Sdelphij// in a properly aligned word in host byte order. 68296341Sdelphij#define SET(n) \ 69296341Sdelphij (InternalState.block[(n)] = (MD5_u32plus)ptr[(n)*4] | \ 70296341Sdelphij ((MD5_u32plus)ptr[(n)*4 + 1] << 8) | \ 71296341Sdelphij ((MD5_u32plus)ptr[(n)*4 + 2] << 16) | \ 72296341Sdelphij ((MD5_u32plus)ptr[(n)*4 + 3] << 24)) 73109998Smarkm#define GET(n) (InternalState.block[(n)]) 74109998Smarkm 75296341Sdelphijusing namespace llvm; 76296341Sdelphij 77109998Smarkm/// This processes one or more 64-byte data blocks, but does NOT update 78296341Sdelphij///the bit counters. There are no alignment requirements. 79296341Sdelphijconst uint8_t *MD5::body(ArrayRef<uint8_t> Data) { 80109998Smarkm const uint8_t *ptr; 81109998Smarkm MD5_u32plus a, b, c, d; 82109998Smarkm MD5_u32plus saved_a, saved_b, saved_c, saved_d; 83109998Smarkm unsigned long Size = Data.size(); 84109998Smarkm 85109998Smarkm ptr = Data.data(); 86296341Sdelphij 87109998Smarkm a = InternalState.a; 88109998Smarkm b = InternalState.b; 89296341Sdelphij c = InternalState.c; 90296341Sdelphij d = InternalState.d; 91296341Sdelphij 92109998Smarkm do { 93109998Smarkm saved_a = a; 94296341Sdelphij saved_b = b; 95296341Sdelphij saved_c = c; 96296341Sdelphij saved_d = d; 97296341Sdelphij 98296341Sdelphij // Round 1 99109998Smarkm STEP(F, a, b, c, d, SET(0), 0xd76aa478, 7) 100296341Sdelphij STEP(F, d, a, b, c, SET(1), 0xe8c7b756, 12) 101296341Sdelphij STEP(F, c, d, a, b, SET(2), 0x242070db, 17) 102296341Sdelphij STEP(F, b, c, d, a, SET(3), 0xc1bdceee, 22) 103296341Sdelphij STEP(F, a, b, c, d, SET(4), 0xf57c0faf, 7) 104296341Sdelphij STEP(F, d, a, b, c, SET(5), 0x4787c62a, 12) 105296341Sdelphij STEP(F, c, d, a, b, SET(6), 0xa8304613, 17) 106296341Sdelphij STEP(F, b, c, d, a, SET(7), 0xfd469501, 22) 107296341Sdelphij STEP(F, a, b, c, d, SET(8), 0x698098d8, 7) 108296341Sdelphij STEP(F, d, a, b, c, SET(9), 0x8b44f7af, 12) 109296341Sdelphij STEP(F, c, d, a, b, SET(10), 0xffff5bb1, 17) 110296341Sdelphij STEP(F, b, c, d, a, SET(11), 0x895cd7be, 22) 111296341Sdelphij STEP(F, a, b, c, d, SET(12), 0x6b901122, 7) 112296341Sdelphij STEP(F, d, a, b, c, SET(13), 0xfd987193, 12) 113109998Smarkm STEP(F, c, d, a, b, SET(14), 0xa679438e, 17) 114296341Sdelphij STEP(F, b, c, d, a, SET(15), 0x49b40821, 22) 115109998Smarkm 116109998Smarkm // Round 2 117296341Sdelphij STEP(G, a, b, c, d, GET(1), 0xf61e2562, 5) 118109998Smarkm STEP(G, d, a, b, c, GET(6), 0xc040b340, 9) 119109998Smarkm STEP(G, c, d, a, b, GET(11), 0x265e5a51, 14) 120296341Sdelphij STEP(G, b, c, d, a, GET(0), 0xe9b6c7aa, 20) 121296341Sdelphij STEP(G, a, b, c, d, GET(5), 0xd62f105d, 5) 122296341Sdelphij STEP(G, d, a, b, c, GET(10), 0x02441453, 9) 123109998Smarkm STEP(G, c, d, a, b, GET(15), 0xd8a1e681, 14) 124109998Smarkm STEP(G, b, c, d, a, GET(4), 0xe7d3fbc8, 20) 125109998Smarkm STEP(G, a, b, c, d, GET(9), 0x21e1cde6, 5) 126109998Smarkm STEP(G, d, a, b, c, GET(14), 0xc33707d6, 9) 127296341Sdelphij STEP(G, c, d, a, b, GET(3), 0xf4d50d87, 14) 128109998Smarkm STEP(G, b, c, d, a, GET(8), 0x455a14ed, 20) 129296341Sdelphij STEP(G, a, b, c, d, GET(13), 0xa9e3e905, 5) 130296341Sdelphij STEP(G, d, a, b, c, GET(2), 0xfcefa3f8, 9) 131296341Sdelphij STEP(G, c, d, a, b, GET(7), 0x676f02d9, 14) 132296341Sdelphij STEP(G, b, c, d, a, GET(12), 0x8d2a4c8a, 20) 133296341Sdelphij 134109998Smarkm // Round 3 135296341Sdelphij STEP(H, a, b, c, d, GET(5), 0xfffa3942, 4) 136109998Smarkm STEP(H, d, a, b, c, GET(8), 0x8771f681, 11) 137109998Smarkm STEP(H, c, d, a, b, GET(11), 0x6d9d6122, 16) 138109998Smarkm STEP(H, b, c, d, a, GET(14), 0xfde5380c, 23) 139296341Sdelphij STEP(H, a, b, c, d, GET(1), 0xa4beea44, 4) 140109998Smarkm STEP(H, d, a, b, c, GET(4), 0x4bdecfa9, 11) 141296341Sdelphij STEP(H, c, d, a, b, GET(7), 0xf6bb4b60, 16) 142296341Sdelphij STEP(H, b, c, d, a, GET(10), 0xbebfbc70, 23) 143296341Sdelphij STEP(H, a, b, c, d, GET(13), 0x289b7ec6, 4) 144296341Sdelphij STEP(H, d, a, b, c, GET(0), 0xeaa127fa, 11) 145296341Sdelphij STEP(H, c, d, a, b, GET(3), 0xd4ef3085, 16) 146296341Sdelphij STEP(H, b, c, d, a, GET(6), 0x04881d05, 23) 147296341Sdelphij STEP(H, a, b, c, d, GET(9), 0xd9d4d039, 4) 148109998Smarkm STEP(H, d, a, b, c, GET(12), 0xe6db99e5, 11) 149296341Sdelphij STEP(H, c, d, a, b, GET(15), 0x1fa27cf8, 16) 150109998Smarkm STEP(H, b, c, d, a, GET(2), 0xc4ac5665, 23) 151296341Sdelphij 152296341Sdelphij // Round 4 153296341Sdelphij STEP(I, a, b, c, d, GET(0), 0xf4292244, 6) 154109998Smarkm STEP(I, d, a, b, c, GET(7), 0x432aff97, 10) 155109998Smarkm STEP(I, c, d, a, b, GET(14), 0xab9423a7, 15) 156109998Smarkm STEP(I, b, c, d, a, GET(5), 0xfc93a039, 21) 157296341Sdelphij STEP(I, a, b, c, d, GET(12), 0x655b59c3, 6) 158296341Sdelphij STEP(I, d, a, b, c, GET(3), 0x8f0ccc92, 10) 159109998Smarkm STEP(I, c, d, a, b, GET(10), 0xffeff47d, 15) 160109998Smarkm STEP(I, b, c, d, a, GET(1), 0x85845dd1, 21) 161109998Smarkm STEP(I, a, b, c, d, GET(8), 0x6fa87e4f, 6) 162109998Smarkm STEP(I, d, a, b, c, GET(15), 0xfe2ce6e0, 10) 163296341Sdelphij STEP(I, c, d, a, b, GET(6), 0xa3014314, 15) 164296341Sdelphij STEP(I, b, c, d, a, GET(13), 0x4e0811a1, 21) 165296341Sdelphij STEP(I, a, b, c, d, GET(4), 0xf7537e82, 6) 166296341Sdelphij STEP(I, d, a, b, c, GET(11), 0xbd3af235, 10) 167296341Sdelphij STEP(I, c, d, a, b, GET(2), 0x2ad7d2bb, 15) 168296341Sdelphij STEP(I, b, c, d, a, GET(9), 0xeb86d391, 21) 169296341Sdelphij 170296341Sdelphij a += saved_a; 171296341Sdelphij b += saved_b; 172296341Sdelphij c += saved_c; 173296341Sdelphij d += saved_d; 174109998Smarkm 175296341Sdelphij ptr += 64; 176296341Sdelphij } while (Size -= 64); 177109998Smarkm 178296341Sdelphij InternalState.a = a; 179296341Sdelphij InternalState.b = b; 180296341Sdelphij InternalState.c = c; 181296341Sdelphij InternalState.d = d; 182296341Sdelphij 183109998Smarkm return ptr; 184296341Sdelphij} 185296341Sdelphij 186109998SmarkmMD5::MD5() = default; 187296341Sdelphij 188296341Sdelphij/// Incrementally add the bytes in \p Data to the hash. 189296341Sdelphijvoid MD5::update(ArrayRef<uint8_t> Data) { 190296341Sdelphij MD5_u32plus saved_lo; 191296341Sdelphij unsigned long used, free; 192109998Smarkm const uint8_t *Ptr = Data.data(); 193296341Sdelphij unsigned long Size = Data.size(); 194296341Sdelphij 195296341Sdelphij saved_lo = InternalState.lo; 196296341Sdelphij if ((InternalState.lo = (saved_lo + Size) & 0x1fffffff) < saved_lo) 197109998Smarkm InternalState.hi++; 198296341Sdelphij InternalState.hi += Size >> 29; 199109998Smarkm 200296341Sdelphij used = saved_lo & 0x3f; 201296341Sdelphij 202296341Sdelphij if (used) { 203296341Sdelphij free = 64 - used; 204296341Sdelphij 205296341Sdelphij if (Size < free) { 206109998Smarkm memcpy(&InternalState.buffer[used], Ptr, Size); 207296341Sdelphij return; 208296341Sdelphij } 209296341Sdelphij 210296341Sdelphij memcpy(&InternalState.buffer[used], Ptr, free); 211296341Sdelphij Ptr = Ptr + free; 212296341Sdelphij Size -= free; 213296341Sdelphij body(ArrayRef(InternalState.buffer, 64)); 214296341Sdelphij } 215296341Sdelphij 216296341Sdelphij if (Size >= 64) { 217296341Sdelphij Ptr = body(ArrayRef(Ptr, Size & ~(unsigned long)0x3f)); 218296341Sdelphij Size &= 0x3f; 219296341Sdelphij } 220296341Sdelphij 221296341Sdelphij memcpy(InternalState.buffer, Ptr, Size); 222296341Sdelphij} 223109998Smarkm 224296341Sdelphij/// Add the bytes in the StringRef \p Str to the hash. 225109998Smarkm// Note that this isn't a string and so this won't include any trailing NULL 226109998Smarkm// bytes. 227296341Sdelphijvoid MD5::update(StringRef Str) { 228109998Smarkm ArrayRef<uint8_t> SVal((const uint8_t *)Str.data(), Str.size()); 229109998Smarkm update(SVal); 230296341Sdelphij} 231296341Sdelphij 232296341Sdelphij/// Finish the hash and place the resulting hash into \p result. 233296341Sdelphij/// \param Result is assumed to be a minimum of 16-bytes in size. 234296341Sdelphijvoid MD5::final(MD5Result &Result) { 235109998Smarkm unsigned long used, free; 236296341Sdelphij 237109998Smarkm used = InternalState.lo & 0x3f; 238109998Smarkm 239296341Sdelphij InternalState.buffer[used++] = 0x80; 240296341Sdelphij 241296341Sdelphij free = 64 - used; 242109998Smarkm 243109998Smarkm if (free < 8) { 244296341Sdelphij memset(&InternalState.buffer[used], 0, free); 245296341Sdelphij body(ArrayRef(InternalState.buffer, 64)); 246296341Sdelphij used = 0; 247296341Sdelphij free = 64; 248296341Sdelphij } 249109998Smarkm 250296341Sdelphij memset(&InternalState.buffer[used], 0, free - 8); 251109998Smarkm 252296341Sdelphij InternalState.lo <<= 3; 253109998Smarkm support::endian::write32le(&InternalState.buffer[56], InternalState.lo); 254109998Smarkm support::endian::write32le(&InternalState.buffer[60], InternalState.hi); 255109998Smarkm 256109998Smarkm body(ArrayRef(InternalState.buffer, 64)); 257109998Smarkm 258109998Smarkm support::endian::write32le(&Result[0], InternalState.a); 259109998Smarkm support::endian::write32le(&Result[4], InternalState.b); 260109998Smarkm support::endian::write32le(&Result[8], InternalState.c); 261296341Sdelphij support::endian::write32le(&Result[12], InternalState.d); 262109998Smarkm} 263109998Smarkm 264296341SdelphijMD5::MD5Result MD5::final() { 265296341Sdelphij MD5Result Result; 266296341Sdelphij final(Result); 267109998Smarkm return Result; 268296341Sdelphij} 269109998Smarkm 270109998SmarkmMD5::MD5Result MD5::result() { 271109998Smarkm auto StateToRestore = InternalState; 272109998Smarkm 273296341Sdelphij auto Hash = final(); 274109998Smarkm 275296341Sdelphij // Restore the state 276296341Sdelphij InternalState = StateToRestore; 277296341Sdelphij 278296341Sdelphij return Hash; 279109998Smarkm} 280296341Sdelphij 281296341SdelphijSmallString<32> MD5::MD5Result::digest() const { 282109998Smarkm SmallString<32> Str; 283296341Sdelphij toHex(*this, /*LowerCase*/ true, Str); 284109998Smarkm return Str; 285296341Sdelphij} 286296341Sdelphij 287296341Sdelphijvoid MD5::stringifyResult(MD5Result &Result, SmallVectorImpl<char> &Str) { 288296341Sdelphij toHex(Result, /*LowerCase*/ true, Str); 289109998Smarkm} 290296341Sdelphij 291109998SmarkmMD5::MD5Result MD5::hash(ArrayRef<uint8_t> Data) { 292109998Smarkm MD5 Hash; 293296341Sdelphij Hash.update(Data); 294296341Sdelphij MD5::MD5Result Res; 295296341Sdelphij Hash.final(Res); 296296341Sdelphij 297296341Sdelphij return Res; 298109998Smarkm} 299109998Smarkm