From 73a6c28e22991f2f6dc0ab303c1c5274f083de77 Mon Sep 17 00:00:00 2001 From: Linus Nordberg Date: Tue, 29 Apr 2014 13:32:37 +0200 Subject: First cut at adding DB support. Including half crazy rewrite of most of the data structures. --- src/db.erl | 86 +++++++++++++++++++ src/plop.erl | 227 +++++++++++++++++++++++++++++++++++-------------- src/plop.hrl | 86 +++++++++++++++---- src/test/plop_test.erl | 52 ++++++++--- 4 files changed, 359 insertions(+), 92 deletions(-) create mode 100644 src/db.erl (limited to 'src') diff --git a/src/db.erl b/src/db.erl new file mode 100644 index 0000000..e1604d1 --- /dev/null +++ b/src/db.erl @@ -0,0 +1,86 @@ +-module(db). +-behaviour(gen_server). + +%% API. +-export([start_link/0, stop/0, init_tables/0]). +-export([add/1, find/1]). +%% API for testing. +-export([dump/1, destroy_tables/0, info_tables/0, dump_to_file/1]). +%% gen_server callbacks. +-export([init/1, handle_call/3, terminate/2, handle_cast/2, handle_info/2, + code_change/3]). + +-include_lib("stdlib/include/qlc.hrl"). +-include("plop.hrl"). + +%% @doc Run once, or rather every time you start on a new database. +%% If run more than once, we'll get {aborted, {already_exists, TABLE}}. +init_tables() -> + %% We've once upon a time invoked mnesia:create_schema/1 with the + %% nodes that will be part of the database. + RamCopies = [], + DiscCopies = [], + DiscOnlyCopies = [node()], + mnesia:start(), + mnesia:create_table(plop, [{type, set}, + {ram_copies, RamCopies}, + {disc_copies, DiscCopies}, + {disc_only_copies, DiscOnlyCopies}, + {attributes, record_info(fields, plop)}]), + mnesia:add_table_index(plop, hash). +destroy_tables() -> + mnesia:delete_table(plop). +info_tables() -> + mnesia:table_info(plop, all). +dump_to_file(Filename) -> + mnesia:dump_to_textfile(Filename). + +init(_Args) -> + {ok, []}. % TODO: return state + +start_link() -> + gen_server:start_link({local, ?MODULE}, ?MODULE, [], []). + +stop() -> + gen_server:call(?MODULE, stop). + +add(Entry) -> + gen_server:call(?MODULE, {add, Entry}). + +find(Hash) -> + gen_server:call(?MODULE, {find, Hash}). + +dump(Table) -> + gen_server:call(?MODULE, {dump, Table}). + +%%%%%%%%%%%%%%%%%%%% +handle_cast(_Request, State) -> + {noreply, State}. + +handle_info(_Info, State) -> + {noreply, State}. + +code_change(_OldVsn, State, _Extra) -> + {ok, State}. + +terminate(_Reason, _State) -> + ok. + +%%%%%%%%%%%%%%%%%%%% +handle_call(stop, _From, State) -> + {stop, normal, stopped, State}; +handle_call({add, Entry}, _From, State) -> + F = fun() -> + mnesia:write(Entry) + end, + Res = mnesia:transaction(F), + {reply, Res, State}; +handle_call({dump, Table}, _From, State) -> + F = fun() -> + Q = qlc:q([E || E <- mnesia:table(Table)]), + qlc:e(Q) + end, + Res = mnesia:transaction(F), + {reply, Res, State}; +handle_call({find, Hash}, _From, State) -> + {reply, mnesia:dirty_read({plop, Hash}), State}. diff --git a/src/plop.erl b/src/plop.erl index 390299d..bee9cb4 100644 --- a/src/plop.erl +++ b/src/plop.erl @@ -1,4 +1,6 @@ -%%% @doc Server holding log entries in a database and hashes in a Merkle tree. +%%% @doc Server holding log entries in a database and hashes in a +%%% Merkle tree. A backend for things like Certificate Transparency +%%% (RFC 6962). %%% %%% When you submit data for insertion in the log, the data and a hash %%% of it is stored in a way that [mumble FIXME and FIXME]. In return @@ -23,12 +25,13 @@ -include_lib("eunit/include/eunit.hrl"). -define(PLOPVERSION, 1). --record(plop, {pubkey :: public_key:rsa_public_key(), - privkey :: public_key:rsa_private_key(), - logid :: binary(), - hashtree :: ht:head()}). +-record(state, {pubkey :: public_key:rsa_public_key(), + privkey :: public_key:rsa_private_key(), + logid :: binary(), + hashtree :: ht:head()}). start_link() -> + db:start_link(), start_link("test/rsakey.pem", "sikrit"). start_link(Keyfile, Passphrase) -> gen_server:start_link({local, ?MODULE}, ?MODULE, [Keyfile, Passphrase], []). @@ -41,10 +44,10 @@ init([Keyfile, Passphrase]) -> {Private_key, Public_key} = read_keyfile(Keyfile, Passphrase), LogID = crypto:hash(sha256, public_key:der_encode('RSAPublicKey', Public_key)), - {ok, #plop{pubkey = Public_key, - privkey = Private_key, - logid = LogID, - hashtree = ht:create()}}. + {ok, #state{pubkey = Public_key, + privkey = Private_key, + logid = LogID, + hashtree = ht:create()}}. handle_cast(_Request, State) -> {noreply, State}. @@ -59,7 +62,7 @@ terminate(_Reason, _State) -> ok. %%%%%%%%%%%%%%%%%%%% -add(Data) when is_record(Data, spt) -> +add(Data) when is_record(Data, timestamped_entry) -> gen_server:call(?MODULE, {add, Data}). sth() -> @@ -71,39 +74,73 @@ sth(Data) -> handle_call(stop, _From, State) -> {stop, normal, stopped, State}; -handle_call({add, Data = #spt{entry = Entry}}, _From, - Plop = #plop{privkey = Privkey, - logid = LogID, - hashtree = Tree}) -> - %% fixme: add Entry to db, - NewTree = ht:append(Tree, serialise(Entry)), - io:format("Tree: ~p~nNewTree: ~p~n", [Tree, NewTree]), - SPT = spt(LogID, Privkey, Data), - {reply, SPT, Plop#plop{hashtree = NewTree}}; +%% FIXME: What's the right interface for add()? Need to be able to set +%% version and signature type, at least. That's missing from +%% #timestamped_entry, so add it somehow. +handle_call({add, #timestamped_entry{} = TimestampedEntry}, + _From, State = #state{privkey = Privkey, + logid = LogID, + hashtree = Tree}) -> + {NewTree, SPT} = do_add(TimestampedEntry, Privkey, LogID, Tree), + io:format("Index: ~p~nSPT: ~p~n", [ht:size(NewTree), SPT]), + {reply, SPT, State#state{hashtree = NewTree}}; handle_call({sth, Data}, _From, - Plop = #plop{privkey = PrivKey, - hashtree = Tree}) -> + Plop = #state{privkey = PrivKey, + hashtree = Tree}) -> {reply, sth(PrivKey, Tree, Data), Plop}. %%%%%%%%%%%%%%%%%%%% -%% @doc Signed Plop Timestamp according to RFC6962 3.2 and RFC5246 4.7. --spec spt(binary(), binary(), spt()) -> binary(). -spt(LogID, PrivKey, Data = #spt{timestamp = Timestamp_in}) -> +do_add(TimestampedEntry, Privkey, LogID, Tree) -> + H = crypto:hash(sha256, serialise(TimestampedEntry)), + Record = db:find(H), + TmpFixm = case Record of + #plop{index = I, spt = S} -> + io:format("Found entry w/ index=~p, SPT: ~p~n", [I, S]), + %% DB consistency check: + %%Record = #plop{hash = H, spt = serialise(Data)}, % FIXME: Remove. + {Tree, % State not changed. + S}; % Cached SPT. + _ -> + NewSPT = spt(LogID, Privkey, TimestampedEntry), + DbData = #plop{index = ht:size(Tree) + 1, + hash = H, + spt = NewSPT}, + db:add(DbData), + LeafData = #mtl{version = 1, + leaf_type = timestamped_entry, + entry = TimestampedEntry}, + {ht:append(Tree, serialise(LeafData)), % New tree. + NewSPT} % New SPT. + end, + TmpFixm. + +%% @doc Signed Plop Timestamp, conformant to an SCT in RFC6962 3.2 and +%% RFC5246 4.7. +-spec spt(binary(), public_key:rsa_private_key(), timestamped_entry()) -> binary(). +spt(LogID, PrivKey, #timestamped_entry{ + timestamp = Timestamp_in, + entry_type = EntryType, + entry = Entry + }) -> Timestamp = timestamp(Timestamp_in), BinToSign = - list_to_binary(serialise(Data#spt{ - signature_type = certificate_timestamp, - timestamp = Timestamp})), + list_to_binary(serialise(#spt_signed{ + version = 1, + signature_type = certificate_timestamp, + timestamp = Timestamp, + entry_type = EntryType, + signed_entry = Entry})), Signature = signhash(BinToSign, PrivKey), - SPT = <>, - %%io:format("SPT: ~p~nBinToSign: ~p~nSignature = ~p~n", - %% [SPT, BinToSign, Signature]), - SPT. + SPT = serialise(#spt_on_wire{ + version = ?PLOPVERSION, + logid = LogID, + timestamp = Timestamp, + signature = Signature}), + io:format("SPT: ~p~nBinToSign: ~p~nSignature = ~p~n", + [SPT, BinToSign, Signature]), + list_to_binary(SPT). %% @doc Signed Tree Head as described in RFC6962 section 3.2. sth(PrivKey, Tree, []) -> @@ -123,8 +160,8 @@ sth(PrivKey, Tree, #sth{version = Version, timestamp = Timestamp_in}) -> Timestamp:64, Roothash/binary, Signature/binary>>, - %% io:format("STH: ~p~nBinToSign: ~p~nSignature: ~p~nTimestamp: ~p~n", - %% [STH, BinToSign, Signature, Timestamp]), + io:format("STH: ~p~nBinToSign: ~p~nSignature: ~p~nTimestamp: ~p~n", + [STH, BinToSign, Signature, Timestamp]), STH. read_keyfile(Filename, Passphrase) -> @@ -136,7 +173,7 @@ read_keyfile(Filename, Passphrase) -> public_key(#'RSAPrivateKey'{modulus = Mod, publicExponent = Exp}) -> #'RSAPublicKey'{modulus = Mod, publicExponent = Exp}. --spec signhash(iolist() | binary(), binary()) -> binary(). +-spec signhash(iolist() | binary(), public_key:rsa_private_key()) -> binary(). signhash(Data, PrivKey) -> %% Was going to just crypto:sign/3 the hash but looking at %% digitally_signed() in lib/ssl/src/ssl_handshake.erl it seems @@ -146,6 +183,26 @@ signhash(Data, PrivKey) -> PrivKey, [{rsa_pad, rsa_pkcs1_padding}]). +%%%%%%%%%%%%%%%%%%%% +%% Serialisation of data. + +%% FIXME: Make the type conversion functions return binaries instead +%% of integers. Moving knowledge about width of these to one place. + +-spec signature_type(signature_type()) -> integer(). +signature_type(certificate_timestamp) -> 0; +signature_type(tree_hash) -> 1; +signature_type(test) -> 2. + +-spec entry_type(entry_type()) -> integer(). +entry_type(x509) -> 0; +entry_type(precert) -> 1; +entry_type(test) -> 2. + +-spec leaf_type(leaf_type()) -> integer(). +leaf_type(timestamped_entry) -> 0; +leaf_type(test) -> 1. + -spec timestamp(now | integer()) -> integer(). timestamp(Timestamp) -> case Timestamp of @@ -157,41 +214,83 @@ timestamp(Timestamp) -> _ -> Timestamp end. --spec serialise(spt() | sth() | plop_entry()) -> iolist(). -serialise(#spt{version = Version, - signature_type = SigtypeAtom, - timestamp = Timestamp, - entry = Entry}) -> +-spec serialise(timestamped_entry() | spt_on_wire() | spt_signed() | mtl() | sth()) -> iolist(). +serialise(#timestamped_entry{ + timestamp = Timestamp, + entry_type = TypeAtom, + entry = Entry + }) -> + EntryType = entry_type(TypeAtom), + [<>]; +serialise(#spt_on_wire{ + version = Version, + logid = LogID, + timestamp = Timestamp, + signature = Signature + }) -> + [<>]; +serialise(#spt_signed{ + version = Version, + signature_type = SigtypeAtom, + timestamp = Timestamp, + entry_type = EntrytypeAtom, + signed_entry = Entry + }) -> Sigtype = signature_type(SigtypeAtom), - [<>, serialise(Entry)]; -serialise(#plop_entry{type = TypeAtom, data = Data}) -> - Type = entry_type(TypeAtom), - [<>, Data]; -serialise(#sth{version = Version, - signature_type = SigtypeAtom, - timestamp = Timestamp, - tree_size = Treesize, - root_hash = Roothash}) -> + Entrytype = entry_type(EntrytypeAtom), + [<>]; +serialise(#mtl{ % Merkle Tree Leaf. + version = Version, + leaf_type = TypeAtom, + entry = TimestampedEntry + }) -> + LeafType = leaf_type(TypeAtom), + [<>, + serialise(TimestampedEntry)]; +serialise(#sth{ % Signed Tree Head. + version = Version, + signature_type = SigtypeAtom, + timestamp = Timestamp, + tree_size = Treesize, + root_hash = Roothash + }) -> Sigtype = signature_type(SigtypeAtom), - [<>]. + [<>]. --spec signature_type(signature_type()) -> integer(). -signature_type(certificate_timestamp) -> 0; -signature_type(tree_hash) -> 1; -signature_type(test) -> 2. - --spec entry_type(entry_type()) -> integer(). -entry_type(x509) -> 0; -entry_type(precert) -> 1; -entry_type(test) -> 2. %%%%%%%%%%%%%%%%%%%% %% Tests. serialise_test_() -> [?_assertEqual( <<1:8, 0:8, 0:64, 0:16, "foo">>, - list_to_binary(serialise(#spt{ + list_to_binary(serialise(#spt_signed{ + version = 1, signature_type = certificate_timestamp, timestamp = 0, - entry = #plop_entry{type = x509, - data = <<"foo">>}})))]. + entry_type = x509, + signed_entry = <<"foo">>})))]. +add_test_() -> + {ok, S} = init(["test/rsakey.pem", "sikrit"]), + [?_assertEqual( + <<"fixme">>, + do_add(#timestamped_entry{ + timestamp = 4711, + entry_type = test, + entry = <<"some data">>}, + S#state.privkey, + S#state.logid, + S#state.hashtree))]. diff --git a/src/plop.hrl b/src/plop.hrl index 7275f5a..5492024 100644 --- a/src/plop.hrl +++ b/src/plop.hrl @@ -1,29 +1,79 @@ --type signature_type() :: certificate_timestamp | tree_hash | test. --type entry_type() :: x509 | precert | test. +%%% plop data structures. Heavily based on RFC 6962. Some are for +%%% database storage, some for interfacing with consumers and some are +%%% for serialisation. -%% @doc The parts of an SPT which is to be signed. --record(spt, { - version = 1 :: integer(), +-type signature_type() :: certificate_timestamp | tree_hash | test. % uint8 +-type entry_type() :: x509 | precert | test. % uint16 +-type leaf_type() :: timestamped_entry | test. % uint8 + +%% @doc What's stored in the database. +-record(plop, { + index :: non_neg_integer(), % Primary key. + hash :: binary(), % SHA-256 over #FIXME.entry. Indexed in db. + spt :: binary() % serialise(#spt_on_wire{}) + }). + +%% @doc Merkle Tree Leaf -- input to hash function for leaf hashes. +-record(mtl, { + version = 1 :: pos_integer(), + leaf_type = timestamped_entry :: leaf_type(), + entry :: timestamped_entry() + }). +-type mtl() :: #mtl{}. + +%% @doc Parts of what goes in an SPT. Used for FIXME. +%% -record(spt, { +%% version = 1 :: pos_integer(), +%% signature_type :: signature_type(), +%% entry :: timestamped_entry() +%% }). +%%-type spt() :: #spt{}. + +-record(spt_on_wire, { + version :: pos_integer(), % uint8 + logid :: binary(), % SHA-256 over DER encoded public log key + timestamp :: integer(), % uint64 + signature :: binary() + }). +-type spt_on_wire() :: #spt_on_wire{}. + +%% @doc What's signed in an SPT. Used for serialisation before hasning +%% and signing. FIXME: Overlapping #spt{} -- merge somehow. +-record(spt_signed, { + version :: pos_integer(), signature_type :: signature_type(), - timestamp = now :: 'now' | integer(), - entry :: plop_entry() - }). --type spt() :: #spt{}. + timestamp :: integer(), + entry_type :: entry_type(), + signed_entry :: binary() + }). +-type spt_signed() :: #spt_signed{}. + +%% Internal representation of a data entry. +-record(timestamped_entry, { + timestamp = now :: now | integer(), + entry_type :: entry_type(), + entry :: binary() + }). +-type timestamped_entry() :: #timestamped_entry{}. + +%% %% Part of interface to plop:add/1. +%% -record(plop_entry, { +%% type :: entry_type(), +%% data :: binary() +%% }). +%% -type plop_entry() :: #plop_entry{}. --record(plop_entry, { - type :: entry_type(), - data = <<>> :: binary() - }). --type plop_entry() :: #plop_entry{}. -%% @doc The parts of an STH which is to be signed. +%% @doc The parts of an STH which is to be signed. Used as the +%% interface to plop:sth/1, for testing. Should probably be internal +%% to plop, if that can be arranged wrt testing. -record(sth, { - version = 1 :: integer(), + version = 1 :: pos_integer(), signature_type :: signature_type(), timestamp = now :: 'now' | integer(), tree_size :: integer(), - root_hash :: binary() % sha256 + root_hash :: binary() % SHA-256 }). -type sth() :: #sth{}. --export_type([plop_entry/0, entry_type/0]). +-export_type([timestamped_entry/0, mtl/0, entry_type/0]). diff --git a/src/test/plop_test.erl b/src/test/plop_test.erl index 87329c6..8a308c0 100644 --- a/src/test/plop_test.erl +++ b/src/test/plop_test.erl @@ -7,12 +7,13 @@ start_stop_test_() -> {setup, fun start/0, fun stop/1, fun is_registered/1}}. %% "Entries can be added and the STH changes." +%% FIXME: This way, if a test fails, we don't stop plop. The tests +%% must run and be validated in strict order though. adding_verifying_test() -> Pid = start(), - add(), - sth(), - %% TODO: add one more and verify that the STH changes - %% add(), + add(0), + sth(0), + add(1), %% sth(), stop(Pid). @@ -30,7 +31,7 @@ is_registered(Pid) -> ?_assertEqual(Pid, whereis(plop))]. %%% Helpers. -add() -> +add(0) -> TestVector = <<1,247,141,118,3,148,171,128,29,143,106,97,200,179,204,166,242,98,70,185,231, 78,193,39,12,245,82,254,230,136,69,69,0,0,0,0,0,0,0,18,103,69,73,8,105,107, @@ -46,11 +47,42 @@ add() -> 90,254,167,119,10,136,211,20,178,251,244,124,87,223,61,102,244,143,98,213,59, 217,84,80,64,22,209,1,63,64,185,63,13,115,43,36,143,93,19,206,234,100,181, 203,214,189,144,145,21,247,165,125,192,43,94,247,209,81,50,100>>, - Entry = #plop_entry{type = test, data = <<"some data">>}, - SPT = #spt{signature_type = test, timestamp = 4711, entry = Entry}, - ?assertEqual(TestVector, plop:add(SPT)). + Entry = #timestamped_entry{timestamp = 4711, + entry_type = test, + entry = <<"some data">>}, + SPT = plop:add(Entry), + ?assertEqual(TestVector, SPT); +add(1) -> + TestVector = + <<1,247,141,118,3,148,171,128,29,143,106,97,200,179,204,166,242,98,70,185,231, + 78,193,39,12,245,82,254,230,136,69,69,0,0,0,0,0,0,0,18,104,141,82,14,84,52, + 131,244,51,145,16,7,238,168,117,8,184,95,165,94,116,234,87,145,43,39,223,243, + 33,159,238,239,195,203,246,232,147,125,234,34,147,83,254,253,248,133,49,81, + 80,7,104,23,24,147,24,116,147,183,20,58,165,53,147,196,226,250,135,18,115, + 182,139,194,190,60,97,103,240,188,86,184,194,21,75,79,136,84,62,53,123,44, + 236,244,24,190,207,193,42,156,230,135,174,90,195,89,174,185,228,129,148,78, + 255,168,104,73,142,85,11,239,222,227,213,208,99,31,12,177,223,187,11,216,119, + 29,231,67,82,140,103,181,173,71,246,112,57,121,153,204,1,249,251,172,26,77, + 96,223,129,102,14,160,115,10,87,105,234,21,99,65,125,198,35,104,160,43,25,74, + 159,64,236,226,126,208,88,199,60,12,88,36,214,174,110,147,215,142,1,205,77, + 116,119,47,222,87,84,99,78,131,212,247,138,156,190,211,244,184,140,46,202,13, + 217,28,20,109,8,129,62,226,37,51,123,94,151,151,47,96,111,122,118,178,242,14, + 213,35,184,204,165,157,199,1,210,74,243,180,36,85,163,69,166,79,136>>, + Entry = #timestamped_entry{timestamp = 4712, + entry_type = test, + entry = <<"some more data">>}, + SPT = plop:add(Entry), + %%io:format(element(2, file:open("foo", write)), "~p", [SPT]), + ?assertEqual(TestVector, SPT). +%% add(2) -> +%% TestVector = <<>>, +%% %% Same data as in 0, should not result in new database entry. +%% Entry = #timestamped_entry{timestamp = 4713, entry_type = test, entry = <<"some data">>}, +%% SPT = plop:add(#spt{signature_type = test, entry = Entry}), +%% ?assertEqual(TestVector, SPT), +%% ?assertEqual(fixme, fixme). -sth() -> +sth(0) -> TestVector = <<0,0,0,0,0,0,0,1,0,0,0,0,0,0,18,103,93,90,159,157,211,129,96,54,161,145,226, 218,28,127,43,87,221,243,153,101,255,249,156,114,234,50,84,163,183,64,215, @@ -68,5 +100,5 @@ sth() -> 187,221,242,23,254,196,182,98,110,150,95,126,53,42,243,123,198,30,247,79,17, 172,129>>, STH = plop:sth(#sth{timestamp = 4711}), - %%io:format(element(2, file:open("foo", write)), "~p", [STH]), + io:format(element(2, file:open("testdata", write)), "~p", [STH]), ?assertEqual(TestVector, STH). -- cgit v1.1