Botan  1.11.15
src/lib/mac/poly1305/poly1305.cpp
Go to the documentation of this file.
00001 /*
00002 * Derived from poly1305-donna-64.h by Andrew Moon <liquidsun@gmail.com>
00003 * in https://github.com/floodyberry/poly1305-donna
00004 *
00005 * (C) 2014 Andrew Moon
00006 * (C) 2014 Jack Lloyd
00007 *
00008 * Botan is released under the Simplified BSD License (see license.txt)
00009 */
00010 
00011 #include <botan/internal/mac_utils.h>
00012 #include <botan/poly1305.h>
00013 #include <botan/loadstor.h>
00014 #include <botan/mul128.h>
00015 #include <botan/internal/donna128.h>
00016 
00017 namespace Botan {
00018 
00019 BOTAN_REGISTER_MAC_NOARGS(Poly1305);
00020 
00021 namespace {
00022 
00023 void poly1305_init(secure_vector<u64bit>& X, const byte key[32])
00024    {
00025    /* r &= 0xffffffc0ffffffc0ffffffc0fffffff */
00026    const u64bit t0 = load_le<u64bit>(key, 0);
00027    const u64bit t1 = load_le<u64bit>(key, 1);
00028 
00029    X[0] = ( t0                    ) & 0xffc0fffffff;
00030    X[1] = ((t0 >> 44) | (t1 << 20)) & 0xfffffc0ffff;
00031    X[2] = ((t1 >> 24)             ) & 0x00ffffffc0f;
00032 
00033    /* h = 0 */
00034    X[3] = 0;
00035    X[4] = 0;
00036    X[5] = 0;
00037 
00038    /* save pad for later */
00039    X[6] = load_le<u64bit>(key, 2);
00040    X[7] = load_le<u64bit>(key, 3);
00041    }
00042 
00043 void poly1305_blocks(secure_vector<u64bit>& X, const byte *m, size_t blocks, bool is_final = false)
00044    {
00045 #if !defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
00046    typedef donna128 uint128_t;
00047 #endif
00048 
00049    const u64bit hibit = is_final ? 0 : (static_cast<u64bit>(1) << 40); /* 1 << 128 */
00050 
00051    const u64bit r0 = X[0];
00052    const u64bit r1 = X[1];
00053    const u64bit r2 = X[2];
00054 
00055    u64bit h0 = X[3+0];
00056    u64bit h1 = X[3+1];
00057    u64bit h2 = X[3+2];
00058 
00059    const u64bit s1 = r1 * (5 << 2);
00060    const u64bit s2 = r2 * (5 << 2);
00061 
00062    while(blocks--)
00063       {
00064       /* h += m[i] */
00065       const u64bit t0 = load_le<u64bit>(m, 0);
00066       const u64bit t1 = load_le<u64bit>(m, 1);
00067 
00068       h0 += (( t0                    ) & 0xfffffffffff);
00069       h1 += (((t0 >> 44) | (t1 << 20)) & 0xfffffffffff);
00070       h2 += (((t1 >> 24)             ) & 0x3ffffffffff) | hibit;
00071 
00072       /* h *= r */
00073       uint128_t d0 = uint128_t(h0) * r0 + uint128_t(h1) * s2 + uint128_t(h2) * s1;
00074       uint128_t d1 = uint128_t(h0) * r1 + uint128_t(h1) * r0 + uint128_t(h2) * s2;
00075       uint128_t d2 = uint128_t(h0) * r2 + uint128_t(h1) * r1 + uint128_t(h2) * r0;
00076 
00077       /* (partial) h %= p */
00078       u64bit        c = carry_shift(d0, 44); h0 = d0 & 0xfffffffffff;
00079       d1 += c;      c = carry_shift(d1, 44); h1 = d1 & 0xfffffffffff;
00080       d2 += c;      c = carry_shift(d2, 42); h2 = d2 & 0x3ffffffffff;
00081       h0  += c * 5; c = carry_shift(h0, 44); h0 = h0 & 0xfffffffffff;
00082       h1  += c;
00083 
00084       m += 16;
00085       }
00086 
00087    X[3+0] = h0;
00088    X[3+1] = h1;
00089    X[3+2] = h2;
00090    }
00091 
00092 void poly1305_finish(secure_vector<u64bit>& X, byte mac[16])
00093    {
00094    /* fully carry h */
00095    u64bit h0 = X[3+0];
00096    u64bit h1 = X[3+1];
00097    u64bit h2 = X[3+2];
00098 
00099    u64bit c;
00100                 c = (h1 >> 44); h1 &= 0xfffffffffff;
00101    h2 += c;     c = (h2 >> 42); h2 &= 0x3ffffffffff;
00102    h0 += c * 5; c = (h0 >> 44); h0 &= 0xfffffffffff;
00103    h1 += c;     c = (h1 >> 44); h1 &= 0xfffffffffff;
00104    h2 += c;     c = (h2 >> 42); h2 &= 0x3ffffffffff;
00105    h0 += c * 5; c = (h0 >> 44); h0 &= 0xfffffffffff;
00106    h1 += c;
00107 
00108    /* compute h + -p */
00109    u64bit g0 = h0 + 5; c = (g0 >> 44); g0 &= 0xfffffffffff;
00110    u64bit g1 = h1 + c; c = (g1 >> 44); g1 &= 0xfffffffffff;
00111    u64bit g2 = h2 + c - (static_cast<u64bit>(1) << 42);
00112 
00113    /* select h if h < p, or h + -p if h >= p */
00114    c = (g2 >> ((sizeof(u64bit) * 8) - 1)) - 1;
00115    g0 &= c;
00116    g1 &= c;
00117    g2 &= c;
00118    c = ~c;
00119    h0 = (h0 & c) | g0;
00120    h1 = (h1 & c) | g1;
00121    h2 = (h2 & c) | g2;
00122 
00123    /* h = (h + pad) */
00124    const u64bit t0 = X[6];
00125    const u64bit t1 = X[7];
00126 
00127    h0 += (( t0                    ) & 0xfffffffffff)    ; c = (h0 >> 44); h0 &= 0xfffffffffff;
00128    h1 += (((t0 >> 44) | (t1 << 20)) & 0xfffffffffff) + c; c = (h1 >> 44); h1 &= 0xfffffffffff;
00129    h2 += (((t1 >> 24)             ) & 0x3ffffffffff) + c;                 h2 &= 0x3ffffffffff;
00130 
00131    /* mac = h % (2^128) */
00132    h0 = ((h0      ) | (h1 << 44));
00133    h1 = ((h1 >> 20) | (h2 << 24));
00134 
00135    store_le(&mac[0], h0, h1);
00136 
00137    /* zero out the state */
00138    clear_mem(&X[0], X.size());
00139    }
00140 
00141 }
00142 
00143 void Poly1305::clear()
00144    {
00145    zap(m_poly);
00146    zap(m_buf);
00147    m_buf_pos = 0;
00148    }
00149 
00150 void Poly1305::key_schedule(const byte key[], size_t)
00151    {
00152    m_buf_pos = 0;
00153    m_buf.resize(16);
00154    m_poly.resize(8);
00155 
00156    poly1305_init(m_poly, key);
00157    }
00158 
00159 void Poly1305::add_data(const byte input[], size_t length)
00160    {
00161    BOTAN_ASSERT_EQUAL(m_poly.size(), 8, "Initialized");
00162 
00163    if(m_buf_pos)
00164       {
00165       buffer_insert(m_buf, m_buf_pos, input, length);
00166 
00167       if(m_buf_pos + length >= m_buf.size())
00168          {
00169          poly1305_blocks(m_poly, &m_buf[0], 1);
00170          input += (m_buf.size() - m_buf_pos);
00171          length -= (m_buf.size() - m_buf_pos);
00172          m_buf_pos = 0;
00173          }
00174       }
00175 
00176    const size_t full_blocks = length / m_buf.size();
00177    const size_t remaining   = length % m_buf.size();
00178 
00179    if(full_blocks)
00180       poly1305_blocks(m_poly, input, full_blocks);
00181 
00182    buffer_insert(m_buf, m_buf_pos, input + full_blocks * m_buf.size(), remaining);
00183    m_buf_pos += remaining;
00184    }
00185 
00186 void Poly1305::final_result(byte out[])
00187    {
00188    BOTAN_ASSERT_EQUAL(m_poly.size(), 8, "Initialized");
00189 
00190    if(m_buf_pos != 0)
00191       {
00192       m_buf[m_buf_pos] = 1;
00193       clear_mem(&m_buf[m_buf_pos+1], m_buf.size() - m_buf_pos - 1);
00194       poly1305_blocks(m_poly, &m_buf[0], 1, true);
00195       }
00196 
00197    poly1305_finish(m_poly, out);
00198 
00199    m_poly.clear();
00200    m_buf_pos = 0;
00201    }
00202 
00203 }