[Swan-dev] a better unified proposal matcher

[Andrew Cagney]

On 1 March 2015 at 22:04, Paul Wouters <paul at nohats.ca> wrote:
> On Fri, 27 Feb 2015, Andrew Cagney wrote:
>
>> By bits I'm guessing you mean the different transform types: ENCR,
>> INTEG, PRF, DH, ...
>
>
> Yes.
>
>> The critical change is to not do any combinatory explosion at all.
>> Instead just go through the transforms once; and look at each
>> independently.
>
>
> Sure, but you have to do that per received proposal set, which are sent
> in order of preference by the sender.

Yes, agreed, I see no way out of doing:

for proposal in received proposals
    [set up for proposal]
    for transform in proposal
        match transform against local proposals
    [did the proposal get a match?]

It is O(N) where N is the total number of transforms in the payload.
That is a lot better than our current worst case which O((N/4)^4).  If
a transform is 8 bytes, and a payload is 3000 bytes ...

At its worst "match transform against local proposals" can just just
iterate through the local proposal set.  Since that is (relative to
O(N) or O((N/4)^4)) small (24 proposals, each containing one
transform) it isn't so bad.  As a second pass, it can be made more
efficient.

BTW, BCG, on IRC, pointed out that a better model is:

   O(i(N)) * O(r(M))

where O(i(N)) is the complexity of going through all N transforms in
the proposal, and O(r(M)) is the complexity of processing each of
those transforms (M is the number of transforms in our set).

We need to attack both (but attacking the received proposal set is far
more urgent).

>> That means, instead of trying to form and then match an entire
>> combination such as aes_cbc+sha2_256+modp2048+sha2_256 we look at the
>> transforms independently, and combine the result at the end.
>
>
> Yes, that would be better.
>
> Paul