I've finally got something concrete (think proof-of-concept :-) to discuss ...
The premise was is that the current code selecting the crypto-suite from an SA proposal payload was too slow. For instance, using some very rubbery math and assuming a 2K payload only containing an SA proposal: -> 2K SA payload -> 200 transforms (approx 2K / 8 bytes-per-transform) -> 50 transforms of each type (assuming 4 types) -> 50^4 proposal combinations = 6 250 000 inner loop iterations if the then assume our end is as bad (while ~32 combinations is more realistic, this does make for big numbers:-) -> 50^4*50&4 -> 40 000 000 000 000 inner loop comparisons a more realistic number is 200 000 000 iterations. On 2 March 2015 at 10:17, Andrew Cagney <[email protected]> wrote: > On 1 March 2015 at 22:04, Paul Wouters <[email protected]> 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?] I've reached the proof-of-concept stage (there's a branch lurking somewhere containing this; run a test then look for XXX: in the logs), which consists of: - a table of proposals, within each proposal the transforms are grouped by type: local_proposals[nr-proposals][nr-transform-types] = { { [ENCR] = { aes-gcm-256, aes-gcm-128, ... } [PRF] = { sha1, sha2, ... } [DH] = { modp2048, ... } }, ..... } - an "inline" matcher function: do read remote_proposal matched[nr-local-proposals][nr-transform-types] = zero while more-remote-transforms-in-proposal read remote_transform for local_proposal in local_proposals if matched[local_proposal][remote_transform.type] continue if local_proposal[remote_transform.type] == remote_transform matched[local_proposal][remote_transform.type] = "yes" for local_proposal in local_proposals if all required matched[local_proposal] return "matched" while more-remote-proposals return no-match worst case, this code takes 200*200 == 40 000 transform comparisons, and more realistically something like 6 000 comparisons worst case While there's still lots too do, there are several interesting immediate results: - the code can stop parsing the payload on first match - i.e, does _not_ need to parse/verify the entire payload (my prototype doesn't :-) - generating an SA payload from the local_proposal table should be straight forward (and more compact) - I'm finding it simpler then the old ikev2_spdb_struct.c code (this is most likely because it doesn't yet contain all the hairy edge cases) Next steps are: - clean up the data structure and code (can the local proposal table contain "struct ike_alg" pointers? don't use dynamic arrays) - using the result of the match - dealing with a user-defined list of proposals (this could be a stumbling point) - having ESP, EH use this code - deleting the old code - see if I found another compiler bug Andrew _______________________________________________ Swan-dev mailing list [email protected] https://lists.libreswan.org/mailman/listinfo/swan-dev
