Elixir md5crypt algorithm

md5crypt.ex

defmodule MD5Crypt do
  @moduledoc """
  Implementation of 'md5crypt' password hashing, compatible with Unix style
  salted and hashed passwords starting with "$1$", and `openssl passwd -1`

  Based on the description here: https://www.vidarholen.net/contents/blog/?p=32
  """

  # Written by Bram Verburg
  # To the extent possible under law, the author(s) have dedicated all copyright and
  # related and neighboring rights to this software to the public domain worldwide.
  # This software is distributed without any warranty.

  @magic "$1$"
  @b64 List.to_tuple('./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz')

  @doc """
  Verify a password against a hash.

  ## Examples

      iex> MD5Crypt.verify("$1$xlmxNekA$1QN3C.WgbrAmbQvhKGIxx/", "test")
      false

      iex> MD5Crypt.verify("$1$xlmxNekA$1QN3C.WgbrAmbQvhKGIxx/", "test123")
      true
  """
  def verify(@magic <> md5crypt, password) do
    [salt, hash] = :binary.split(md5crypt, "$")

    # In practice this step is rarely needed
    salt =
      case byte_size(salt) do
        len when len > 8 -> :binary.part(salt, 0, 8)
        _ -> salt
      end

    alt_sum = :crypto.hash(:md5, [password, salt, password])

    intermediate =
      :crypto.hash(:md5, [
        password,
        @magic,
        salt,
        take(alt_sum, byte_size(password)),
        suffix(password)
      ])

    result =
      0..999
      |> Enum.reduce(intermediate, &step(&1, password, salt, &2))
      |> shuffle()
      |> encode64()

    result == hash
  end

  defp take(string, count) when count > byte_size(string) do
    take(string <> string, count)
  end

  defp take(string, count) do
    :binary.part(string, 0, count)
  end

  defp suffix(<<first::8, _::binary>> = password), do: suffix(byte_size(password), first, [])

  defp suffix(0, _, acc), do: acc |> Enum.reverse() |> to_string()

  defp suffix(i, first, acc) when rem(i, 2) == 1 do
    suffix(Bitwise.bsr(i, 1), first, [0 | acc])
  end

  defp suffix(i, first, acc) do
    suffix(Bitwise.bsr(i, 1), first, [first | acc])
  end

  defp step(i, password, salt, intermediate) do
    :crypto.hash_init(:md5)
    |> maybe_update(intermediate, rem(i, 2) == 0)
    |> maybe_update(password, rem(i, 2) != 0)
    |> maybe_update(salt, rem(i, 3) != 0)
    |> maybe_update(password, rem(i, 7) != 0)
    |> maybe_update(password, rem(i, 2) == 0)
    |> maybe_update(intermediate, rem(i, 2) != 0)
    |> :crypto.hash_final()
  end

  defp maybe_update(state, _, false), do: state
  defp maybe_update(state, data, true), do: :crypto.hash_update(state, data)

  defp shuffle(<<b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13, b14, b15>>) do
    <<b11, b4, b10, b5, b3, b9, b15, b2, b8, b14, b1, b7, b13, b0, b6, b12>>
  end

  defp encode64(data) when byte_size(data) == 16 do
    encode64(<<0::4, data::binary>>, [])
  end

  defp encode64(<<>>, acc), do: to_string(acc)

  defp encode64(<<bits::6, more::bitstring>>, acc) do
    encode64(more, [elem(@b64, bits) | acc])
  end
end