The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Crypt-IDA-0.03
River stage zero No dependents
++
/ Crypt::IDA::Algorithm

NAME

Crypt::IDA::Algorithm - Expose methods useful for writing custom IDA loops

SYNOPSIS

 use Crypt::IDA::Algorithm;
 use Digest::HMAC_SHA1 qw/hmac_sha1_hex/;
 
 # Make cryptographically secure ticket for entry to a party
 my $secret = 'Not just any Tom, Dick and Harry';
 my $ticket = 'Admit Tom, Dick /and/ Harry to the party together';
 my $signed = "$ticket:" . hmac_sha1_hex($ticket,$secret);
 
 # Algorithm works on full matrix columns, so must pad the message
 $signed .= "\0" while length($signed) % 3;
 
 # Turn the signed ticket into three shares
 my $s = Crypt::IDA::Algorithm->splitter(k=>3, key=>[1..6]);
 $s->fill_stream($signed);
 $s->split_stream;
 my @tickets = map { $s->empty_substream($_) } (0..2);
 
 # At the party, Tom, Dick and Harry present shares to be combined
 my $c = Crypt::IDA::Algorithm->combiner(k=>3, key=>[1..6],
                                         sharelist=>[0..2]);
 $c->fill_substream($_, $tickets[$_]) foreach (0..2);
 $c->combine_streams;
 my $got = $c->empty_stream;
 
 # Check the recovered ticket
 $got =~ /^(.*):(.*)\0*$/;
 my ($msg, $sig) = ($1,$2);
 die "Fake!\n" unless $sig eq hmac_sha1_hex($msg,$secret);
 print "Welcome! $msg!\n";

DESCRIPTION

This module is a rewrite of the original ida_split and ida_combine methods provided in Crypt::IDA. It provides a pared-down, simplified interface intended to make it easier to integrate with an external event loop. It does this by:

  • Decoupling processing from I/O (caller handles I/O and passes data to this module as strings)

  • Eliminating the inner loop (caller decides when/how to loop, if needed)

  • Allowing caller to register callback hooks to become notified when something "interesting" happens within the code (eg, new input became available or space became available in the output buffer)

NOTICE

This code has been tested to make sure that it replicates the behaviour of the original Crypt::IDA implementation. However, I have not yet implemented any callback functionality that would make it easier to integrate with an external event loop. I will add callbacks in a later release.

CODE ORGANISATION

The internal organisation of the code has been improved. The main Crypt::IDA loops (ida_split and ida_combine) both call a generic internal ida_process_streams loop. It has very complicated logic to enable it to handle different matrix layouts and circular buffer reads/writes, as well as dealing with partial matrix columns.

By contrast, this new code:

  • always deals with full matrix columns

  • abstracts away the circular buffering into a new, more generic "Sliding Window" class (Crypt::IDA::SlidingWindow, accessible via the sw accessor)

  • treats split and combine separately, providing different method interfaces appropriate to each

This new code also avoids using `name => value` style parameter-passing interface, apart from in the constructor methods.

Although my main design goal for this class was to make it work better with external event loops, the cleaner interface, with less boilerplate for setting up fillers/emptiers, means that it might be more comfortable to use in general. Even if you're not using an event loop.

GENERAL OPERATION

By way of recap, the IDA split and combine operations are a set of matrix operations:

 transform x input -> output

The constructor will create a set of input and output matrix buffers as follows:

   +----------+>---------+      +>---------+----------+
   v          | Output   |      |  Input   v          v
   |  Input   +>---------+      +>---------+ Output   |
   |    =     |   =      |      |   =      |    =     |
   | COLWISE  +>---------+      +>---------+ COLWISE  |
   |          | ROWWISE  |      | ROWWISE  |          |
   +----------+>---------+      +>---------+----------+
              |    :     |      |    :     | 

            SPLIT                       COMBINE

In both cases, one full column of input produces one full column of output. Matrix columns are written to and read circularly, with checks made to prevent overruns and underruns. To simplify this processing, the input and output buffers are created with the same number of columns (the "window size") in each.

Progress is made using the usual input -> process -> output idiom with the help of a "sliding window" class (Crypt::IDA::SlidingWindow) that tracks three types of pointer:

  • input on the left advances the read_head pointer

  • processing advances the read_tail on the left, process pointer in the middle, and write_head pointer on the right

  • output on the right advances the write_tail pointer

The class ensures that inputs and outputs cannot advance any further than their respective input and output windows. That is, it prevents buffer overflows caused by:

  • trying to read too much into the input buffer

  • processing too much, causing an overflow in the output buffer

The sliding window class also handles synchronisation of bundles of substreams so that the overall bundle can advance when the slowest substream in the bundle makes progress. A callback can be set up to monitor for when this happens, allowing handling of asynchronous I/O in an event-drive fashion. See CALLBACKS and INTEGRATION WITH EVENT LOOPS for more details.

Note that the Crypt::IDA::Algorithm class is designed from the point of view of working with infinite-length streams. Or indefinite-length streams, if you prefer. That is to say, it has no inbuilt checks for EOF on the input stream(s). EOF checking on input (as well as I/O errors in general) is left completely up to the calling program.

CONSTRUCTORS

As with Crypt::IDA, the constructors here can take either a transform matrix or a key parameter. See Crypt::IDA for details. The list of required parameters and parameter defaults is slighly different, though:

  • 'width' defaults to 1 (byte) and is renamed 'w'

  • 'shares' (n) is not passed in (see below)

  • no option ('random') relating to creation of random key (caller must supply a matrix or a key)

  • no options relating to I/O ('filler(s)', 'emptier(s)')

  • no option ('bytes') relating to stream size

Crypt::IDA::Algorithm->splitter()

The full list of options available when creating a new splitter is as follows:

 my $splitter = Crypt::IDA::Algorithm->splitter(
    # Required:
    k     => 4,                  # Quorum value (4 shares needed to combine)
    xform => new_cauchy(...),    # Supply either a matrix ...
    key   => [ @xvals, @yvals ], # ... or a key (scalar (@yvals) == k)
 
    # Optional sharelist, only with 'key' parameter:
    sharelist => [0,1],          # use xvals[0], xvals[1] to create two shares
 
    # Defaults provided:
    w => 1,                      # field width == 1 byte
    bufsize  => 16384,           # columns in in/out matrices
    inorder  => 0,               # no byte-swapping ...
    outorder => 0,               # ie, native byte order
 );

The 'n' value (number of shares) is not passed in explicitly. Instead it is calculated from the other parameters:

  • from the number of rows in a supplied 'xform' matrix

  • from the number of @xvals in the key, after the k @yvals are accounted for

  • from the number of elements in 'sharelist' (if both 'key' and 'sharelist' were provided)

Crypt::IDA::Algorithm->combiner()

The full list of options available when creating a new combiner is as follows:

 my $combiner = Crypt::IDA::Algorithm->combiner(
    # Required:
    k => 4,                      # Quorum value (4 shares needed to combine)
 
    # Supply either a matrix ...
    xform => new_inverse_cauchy(...),
  
    # ... or a key (sharelist required and must have k elements)
    key   => [ @xvals, @yvals ],  # scalar (@yvals) == k
    sharelist => [0..3],          # use xvals[0..3] to create inverse xform
 
    # defaults provided:
    w => 1,                      # field width == 1 byte
    bufsize  => 16384,           # columns in in/out matrices
    inorder  => 0,               # no byte-swapping ...
    outorder => 0,               # ie, native byte order
 );

CALLBACKS

None currently implemented in this class, but see Crypt::IDA::SlidingWindow.

INTEGRATION WITH EVENT LOOPS

As this package stands, there's nothing actually stopping it from being used within an event loop. If the input and output is over network sockets, for example, all the major event loops have features for handling this in a non-blocking way. Most will have an equivalent of an "on_read" callback that can be used to receive new data, which can then be passed to this class for transformation, then the output can be sent to another non-blocking socket (or sockets). So long as the output is non-blocking, then the IDA output matrix can always be flushed, so split/combine operations only block for as long as the calculations take.

While I imagine that the above way of calling this class will be typical, I also suspect that other people might have their own idea of how this code should be called (or encapsulated) within their own particular event framework. As with Perl, there's definitely more than one way to do event-driven programming.

It seems that the easiest way to support arbitrary event loops is by providing callbacks for when various "interesting" things happen within the algorithm, such as an input matrix becoming full, or space becoming available within the output matrix. This kind of approach is a natural fit, since it's the dominant style of event-driven programming.

However, without untangling what the most common use cases are, it's not really possible to determine in advance exactly which callbacks I should implement. I don't want to add unnecessary complexity or a bunch of incompatible callbacks. As a result, I'm not going to tackle that problem in this release.

As the code stands, there is partial support for using callbacks. The SlidingWindow object (accessed via {sw}) can be set up to trigger a cb_write_bundle or cb_read_bundle callback when the slowest stream in a substream advances.

AUTHOR

Declan Malone, <idablack@sourceforge.net>

COPYRIGHT AND LICENSE

Copyright (C) 2019 Declan Malone

This package is free software; you can redistribute it and/or modify it under the terms of version 2 (or, at your discretion, any later version) of the "GNU General Public License" ("GPL").

Please refer to the file "GNU_GPL.txt" in this distribution for details.

DISCLAIMER

This package is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.