Double count stack for LMS

[derstrand]

In https://github.com/cisco/hash-sigs/blob/master/hss_alloc.c

Are lines 307 and 407 a double counting the stack_usage for the case of LMS? In the case line 343 falls through (not continue statement) ? Line 422 should only be += in the case of HSS, at least 2 levels and overwritten in the case of LMS.

Some applications may have restrictions on storage and so exact stack count and minimal working key size are very important.

[sfluhrer]

I do not believe we are double-counting. What's in line 307 counts the stack usage only for the upper level trees (that is, all of them except the bottom-most) - note that the for loop (starts at line 261) that it is in iterates between 0 and level-2. In the "LMS" use-case (levels==1), this loop is skipped entirely. Line 407 counts the stack usage only for the bottom-most tree. Hence, those two lines account for separate costs. From: derstrand ***@***.***> Sent: Monday, December 4, 2023 1:56 PM To: cisco/hash-sigs ***@***.***> Cc: Subscribed ***@***.***> Subject: [cisco/hash-sigs] Double count stack for LMS (Issue #22) In https://github.com/cisco/hash-sigs/blob/master/hss_alloc.c Are lines 307 and 407 a double counting the stack_usage for the case of LMS? In the case line 343 falls through (not continue statement) ? Line 422 should only be += in the case of HSS, at least 2 levels and overwritten in the case of LMS. In the LMS case, when we hit line 422, stack_usage will still be 0 (and so += is appropriate) Some applications may have restrictions on storage and so exact stack count and minimal working key size are very important. - Reply to this email directly, view it on GitHub<#22>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AB5KPWTPNTQG74WWZXWOTRTYHYMDXAVCNFSM6AAAAABAGOVQBKVHI2DSMVQWIX3LMV43ASLTON2WKOZSGAZDINJRGIZDONQ>. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[sfluhrer]

The reason we have the two separate logics (one for the bottom-most tree, another for all the others) is that we use different strategies for selecting the sizes of the subtrees. For the non-bottom-most, selecting small subtrees doesn't have any disadvantages (and does reduce memory (stack) usage, and so we do that. For the bottom-most, larger subtrees will speed up signature generation (if we generate several signatures after a reload), and so we consider that as an option.