LibCrypto: Add HashFunction and implement MD5

4 files changed, 393 insertions, 2 deletions

diff --git a/Libraries/LibCrypto/Hash/HashFunction.h b/Libraries/LibCrypto/Hash/HashFunction.h
new file mode 100644
index 0000000000..00aedfafb5
--- /dev/null
+++ b/Libraries/LibCrypto/Hash/HashFunction.h
@@ -0,0 +1,51 @@
+/*
+ * Copyright (c) 2020, Ali Mohammad Pur <ali.mpfard@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <AK/ByteBuffer.h>
+#include <AK/StringView.h>
+#include <AK/Types.h>
+
+namespace Crypto {
+
+template<size_t BlockS, typename DigestT>
+class HashFunction {
+public:
+    static constexpr auto BlockSize = BlockS;
+    using DigestType = DigestT;
+
+    static size_t block_size() { return BlockSize; };
+    static size_t digest_size() { return sizeof(DigestType); };
+
+    virtual void update(const u8*, size_t) = 0;
+    virtual void update(const ByteBuffer& buffer) = 0;
+    virtual void update(const StringView& string) = 0;
+
+    virtual DigestType digest() = 0;
+};
+
+}
diff --git a/Libraries/LibCrypto/Hash/MD5.cpp b/Libraries/LibCrypto/Hash/MD5.cpp
new file mode 100644
index 0000000000..338b995def
--- /dev/null
+++ b/Libraries/LibCrypto/Hash/MD5.cpp
@@ -0,0 +1,231 @@
+/*
+ * Copyright (c) 2020, Ali Mohammad Pur <ali.mpfard@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <AK/Types.h>
+#include <LibCrypto/Hash/MD5.h>
+
+static constexpr inline u32 F(u32 x, u32 y, u32 z) { return (x & y) | ((~x) & z); };
+static constexpr inline u32 G(u32 x, u32 y, u32 z) { return (x & z) | ((~z) & y); };
+static constexpr inline u32 H(u32 x, u32 y, u32 z) { return x ^ y ^ z; };
+static constexpr inline u32 I(u32 x, u32 y, u32 z) { return y ^ (x | ~z); };
+static constexpr inline u32 ROTATE_LEFT(u32 x, size_t n)
+{
+    return (x << n) | (x >> (32 - n));
+}
+
+static constexpr inline void round_1(u32& a, u32 b, u32 c, u32 d, u32 x, u32 s, u32 ac)
+{
+    a += F(b, c, d) + x + ac;
+    a = ROTATE_LEFT(a, s);
+    a += b;
+}
+
+static constexpr inline void round_2(u32& a, u32 b, u32 c, u32 d, u32 x, u32 s, u32 ac)
+{
+    a += G(b, c, d) + x + ac;
+    a = ROTATE_LEFT(a, s);
+    a += b;
+}
+
+static constexpr inline void round_3(u32& a, u32 b, u32 c, u32 d, u32 x, u32 s, u32 ac)
+{
+    a += H(b, c, d) + x + ac;
+    a = ROTATE_LEFT(a, s);
+    a += b;
+}
+
+static constexpr inline void round_4(u32& a, u32 b, u32 c, u32 d, u32 x, u32 s, u32 ac)
+{
+    a += I(b, c, d) + x + ac;
+    a = ROTATE_LEFT(a, s);
+    a += b;
+}
+
+namespace Crypto {
+
+void MD5::update(const u8* input, size_t length)
+{
+    auto index = (u32)(m_count[0] >> 3) & 0x3f;
+    size_t offset { 0 };
+    m_count[0] += (u32)length << 3;
+    if (m_count[0] < ((u32)length << 3)) {
+        ++m_count[1];
+    }
+    m_count[1] += (u32)length >> 29;
+
+    auto part_length = 64 - index;
+    if (length >= part_length) {
+        m_buffer.overwrite(index, input, part_length);
+        transform(m_buffer.data());
+
+        for (offset = part_length; offset + 63 < length; offset += 64)
+            transform(&input[offset]);
+
+        index = 0;
+    }
+
+    ASSERT(length < part_length || length - offset <= 64);
+    m_buffer.overwrite(index, &input[offset], length - offset);
+}
+MD5::DigestType MD5::digest()
+{
+    DigestType digest;
+    u8 bits[8];
+
+    encode(m_count, bits, 8);
+
+    // pad the data to 56%64
+    u32 index = (u32)((m_count[0] >> 3) & 0x3f);
+    u32 pad_length = index < 56 ? 56 - index : 120 - index;
+    update(Constants::PADDING, pad_length);
+
+    // append length
+    update(bits, 8);
+
+    // store state (4 registers ABCD)
+    encode(&m_A, digest.data, 4 * sizeof(m_A));
+
+    reset();
+
+    return digest;
+}
+
+void MD5::encode(const u32* from, u8* to, size_t length)
+{
+    for (size_t i = 0, j = 0; j < length; ++i, j += 4) {
+        to[j] = (u8)(from[i] & 0xff);
+        to[j + 1] = (u8)((from[i] >> 8) & 0xff);
+        to[j + 2] = (u8)((from[i] >> 16) & 0xff);
+        to[j + 3] = (u8)((from[i] >> 24) & 0xff);
+    }
+}
+
+void MD5::decode(const u8* from, u32* to, size_t length)
+{
+    for (size_t i = 0, j = 0; j < length; ++i, j += 4)
+        to[i] = (((u32)from[j]) | (((u32)from[j + 1]) << 8) | (((u32)from[j + 2]) << 16) | (((u32)from[j + 3]) << 24));
+}
+
+void MD5::transform(const u8* block)
+{
+    auto a = m_A;
+    auto b = m_B;
+    auto c = m_C;
+    auto d = m_D;
+    u32 x[16];
+
+    decode(block, x, 64);
+
+    round_1(a, b, c, d, x[0], Constants::S11, 0xd76aa478); // 1
+    round_1(d, a, b, c, x[1], Constants::S12, 0xe8c7b756); // 2
+    round_1(c, d, a, b, x[2], Constants::S13, 0x242070db); // 3
+    round_1(b, c, d, a, x[3], Constants::S14, 0xc1bdceee); // 4
+    round_1(a, b, c, d, x[4], Constants::S11, 0xf57c0faf); // 5
+    round_1(d, a, b, c, x[5], Constants::S12, 0x4787c62a); // 6
+    round_1(c, d, a, b, x[6], Constants::S13, 0xa8304613); // 7
+    round_1(b, c, d, a, x[7], Constants::S14, 0xfd469501); // 8
+    round_1(a, b, c, d, x[8], Constants::S11, 0x698098d8); // 9
+    round_1(d, a, b, c, x[9], Constants::S12, 0x8b44f7af); // 10
+    round_1(c, d, a, b, x[10], Constants::S13, 0xffff5bb1); // 11
+    round_1(b, c, d, a, x[11], Constants::S14, 0x895cd7be); // 12
+    round_1(a, b, c, d, x[12], Constants::S11, 0x6b901122); // 13
+    round_1(d, a, b, c, x[13], Constants::S12, 0xfd987193); // 14
+    round_1(c, d, a, b, x[14], Constants::S13, 0xa679438e); // 15
+    round_1(b, c, d, a, x[15], Constants::S14, 0x49b40821); // 16
+
+    round_2(a, b, c, d, x[1], Constants::S21, 0xf61e2562); // 17
+    round_2(d, a, b, c, x[6], Constants::S22, 0xc040b340); // 18
+    round_2(c, d, a, b, x[11], Constants::S23, 0x265e5a51); // 19
+    round_2(b, c, d, a, x[0], Constants::S24, 0xe9b6c7aa); // 20
+    round_2(a, b, c, d, x[5], Constants::S21, 0xd62f105d); // 21
+    round_2(d, a, b, c, x[10], Constants::S22, 0x2441453); // 22
+    round_2(c, d, a, b, x[15], Constants::S23, 0xd8a1e681); // 23
+    round_2(b, c, d, a, x[4], Constants::S24, 0xe7d3fbc8); // 24
+    round_2(a, b, c, d, x[9], Constants::S21, 0x21e1cde6); // 25
+    round_2(d, a, b, c, x[14], Constants::S22, 0xc33707d6); // 26
+    round_2(c, d, a, b, x[3], Constants::S23, 0xf4d50d87); // 27
+    round_2(b, c, d, a, x[8], Constants::S24, 0x455a14ed); // 28
+    round_2(a, b, c, d, x[13], Constants::S21, 0xa9e3e905); // 29
+    round_2(d, a, b, c, x[2], Constants::S22, 0xfcefa3f8); // 30
+    round_2(c, d, a, b, x[7], Constants::S23, 0x676f02d9); // 31
+    round_2(b, c, d, a, x[12], Constants::S24, 0x8d2a4c8a); // 32
+
+    round_3(a, b, c, d, x[5], Constants::S31, 0xfffa3942); // 33
+    round_3(d, a, b, c, x[8], Constants::S32, 0x8771f681); // 34
+    round_3(c, d, a, b, x[11], Constants::S33, 0x6d9d6122); // 35
+    round_3(b, c, d, a, x[14], Constants::S34, 0xfde5380c); // 36
+    round_3(a, b, c, d, x[1], Constants::S31, 0xa4beea44); // 37
+    round_3(d, a, b, c, x[4], Constants::S32, 0x4bdecfa9); // 38
+    round_3(c, d, a, b, x[7], Constants::S33, 0xf6bb4b60); // 39
+    round_3(b, c, d, a, x[10], Constants::S34, 0xbebfbc70); // 40
+    round_3(a, b, c, d, x[13], Constants::S31, 0x289b7ec6); // 41
+    round_3(d, a, b, c, x[0], Constants::S32, 0xeaa127fa); // 42
+    round_3(c, d, a, b, x[3], Constants::S33, 0xd4ef3085); // 43
+    round_3(b, c, d, a, x[6], Constants::S34, 0x4881d05); // 44
+    round_3(a, b, c, d, x[9], Constants::S31, 0xd9d4d039); // 45
+    round_3(d, a, b, c, x[12], Constants::S32, 0xe6db99e5); // 46
+    round_3(c, d, a, b, x[15], Constants::S33, 0x1fa27cf8); // 47
+    round_3(b, c, d, a, x[2], Constants::S34, 0xc4ac5665); // 48
+
+    round_4(a, b, c, d, x[0], Constants::S41, 0xf4292244); // 49
+    round_4(d, a, b, c, x[7], Constants::S42, 0x432aff97); // 50
+    round_4(c, d, a, b, x[14], Constants::S43, 0xab9423a7); // 51
+    round_4(b, c, d, a, x[5], Constants::S44, 0xfc93a039); // 52
+    round_4(a, b, c, d, x[12], Constants::S41, 0x655b59c3); // 53
+    round_4(d, a, b, c, x[3], Constants::S42, 0x8f0ccc92); // 54
+    round_4(c, d, a, b, x[10], Constants::S43, 0xffeff47d); // 55
+    round_4(b, c, d, a, x[1], Constants::S44, 0x85845dd1); // 56
+    round_4(a, b, c, d, x[8], Constants::S41, 0x6fa87e4f); // 57
+    round_4(d, a, b, c, x[15], Constants::S42, 0xfe2ce6e0); // 58
+    round_4(c, d, a, b, x[6], Constants::S43, 0xa3014314); // 59
+    round_4(b, c, d, a, x[13], Constants::S44, 0x4e0811a1); // 60
+    round_4(a, b, c, d, x[4], Constants::S41, 0xf7537e82); // 61
+    round_4(d, a, b, c, x[11], Constants::S42, 0xbd3af235); // 62
+    round_4(c, d, a, b, x[2], Constants::S43, 0x2ad7d2bb); // 63
+    round_4(b, c, d, a, x[9], Constants::S44, 0xeb86d391); // 64
+
+    m_A += a;
+    m_B += b;
+    m_C += c;
+    m_D += d;
+
+    __builtin_memset(x, 0, sizeof(x));
+}
+
+void MD5::reset()
+{
+    m_A = Constants::init_A;
+    m_B = Constants::init_B;
+    m_C = Constants::init_C;
+    m_D = Constants::init_D;
+
+    m_count[0] = 0;
+    m_count[1] = 0;
+
+    __builtin_memset(m_data_buffer, 0, sizeof(m_data_buffer));
+}
+
+}
diff --git a/Libraries/LibCrypto/Hash/MD5.h b/Libraries/LibCrypto/Hash/MD5.h
new file mode 100644
index 0000000000..fd8f8dba20
--- /dev/null
+++ b/Libraries/LibCrypto/Hash/MD5.h
@@ -0,0 +1,108 @@
+/*
+ * Copyright (c) 2020, Ali Mohammad Pur <ali.mpfard@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <AK/Types.h>
+#include <LibCrypto/Hash/HashFunction.h>
+
+namespace Crypto {
+
+struct MD5Digest {
+    u8 data[16];
+};
+
+namespace MD5Constants {
+
+constexpr u32 init_A = 0x67452301;
+constexpr u32 init_B = 0xefcdab89;
+constexpr u32 init_C = 0x98badcfe;
+constexpr u32 init_D = 0x10325476;
+constexpr u32 S11 = 7;
+constexpr u32 S12 = 12;
+constexpr u32 S13 = 17;
+constexpr u32 S14 = 22;
+constexpr u32 S21 = 5;
+constexpr u32 S22 = 9;
+constexpr u32 S23 = 14;
+constexpr u32 S24 = 20;
+constexpr u32 S31 = 4;
+constexpr u32 S32 = 11;
+constexpr u32 S33 = 16;
+constexpr u32 S34 = 23;
+constexpr u32 S41 = 6;
+constexpr u32 S42 = 10;
+constexpr u32 S43 = 15;
+constexpr u32 S44 = 21;
+constexpr u8 PADDING[] = {
+    0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+    0
+};
+
+}
+
+class MD5 final : public HashFunction<16, MD5Digest> {
+public:
+    MD5()
+    {
+        m_buffer = ByteBuffer::wrap(m_data_buffer, sizeof(m_data_buffer));
+    }
+
+    virtual void update(const u8*, size_t) override;
+    virtual void update(const ByteBuffer& buffer) override { update(buffer.data(), buffer.size()); };
+    virtual void update(const StringView& string) override { update((const u8*)string.characters_without_null_termination(), string.length()); };
+    virtual DigestType digest() override;
+
+    inline static DigestType hash(const u8* data, size_t length)
+    {
+        MD5 md5;
+        md5.update(data, length);
+        return md5.digest();
+    }
+
+    inline static DigestType hash(const ByteBuffer& buffer) { return hash(buffer.data(), buffer.size()); }
+    inline static DigestType hash(const StringView& buffer) { return hash((const u8*)buffer.characters_without_null_termination(), buffer.length()); }
+
+private:
+    inline void transform(const u8*);
+    inline void reset();
+
+    static void encode(const u32* from, u8* to, size_t length);
+    static void decode(const u8* from, u32* to, size_t length);
+
+    u32 m_A { Constants::init_A }, m_B { Constants::init_B }, m_C { Constants::init_C }, m_D { Constants::init_D };
+    u32 m_count[2] { 0, 0 };
+    ByteBuffer m_buffer;
+
+    u8 m_data_buffer[64];
+};
+
+}
+
+}
diff --git a/Libraries/LibCrypto/Makefile b/Libraries/LibCrypto/Makefile
index 32982402db..9eb78bcacc 100644
--- a/Libraries/LibCrypto/Makefile
+++ b/Libraries/LibCrypto/Makefile
@@ -1,12 +1,13 @@
 LIBCRYPTO_OBJS = \
-	   	Cipher/AES.o
+	   	Cipher/AES.o \
+		Hash/MD5.o
 
 OBJS = $(LIBCRYPTO_OBJS)
 
 LIBRARY = libcrypto.a
 
 install:
-	for dir in . Cipher Cipher/Mode; do \
+	for dir in . Cipher Cipher/Mode Hash; do \
 	    mkdir -p $(SERENITY_BASE_DIR)/Root/usr/include/LibCrypto/$$dir; \
 	    cp $$dir/*.h $(SERENITY_BASE_DIR)/Root/usr/include/LibCrypto/$$dir/; \
 	done