asciilifeform: http://logs.nosuchlabs.com/log/trilema/2019-08-09#1926712 << it is entirely possible to have sane ~back end~ on which you, e.g., write in a lisp-flavoured skin when mangling trees, and a fortran-flavoured skin when want to run in constant space/time with fine control of flow; the bolix people -- had. in fact, arguably all machines have (presently piss-poor) incarnation of this concept, it is... the machine arch itself.

asciilifeform: ftr asciilifeform is sewing a constant-time keccak so that peh can rsa in battlefield. is someone gonna do this in my place, so i can write www log ??

asciilifeform: ( on pc, in addition to 'unix leaky' and other boobytraps, also gotta contend with not knowing what the fuck the cpu does internally in re constant-time )

asciilifeform: OriansJ: lotsa folx over the years landed in the logs, and thought 'these people sit and philosophize and what'. but plenty of examples of working mechanism , if yer interested to study. http://www.loper-os.org/?cat=49 for instance is a just-short-of-done constant-time 0-dependency cryptoarithmetizer.

asciilifeform: ( the latter not used for any of the published tests, but to simply gauge the effect of 'modern' x86isms . fwiw does have constant-time mul etc )

asciilifeform: ( in fact ada per se has a fascism knob that, if set, prevents early return from subroutines . i have not thus far used, cuz in ffa per se this is already the case, nuffin gets to terminate early when 'constant time' algo )

asciilifeform: the knobs still on conveyor are -- subroutines; hash ; constant-time table lookups. that's it.

asciilifeform: 'but asciilifeform , if you want lobster, you gotta build a $9000b fishing fleet' 'mno, here's 1 from your own dryer lint trap, and it can bend xrays and modexp in constant time, naowat'

asciilifeform: in re single-shot gcd, you either ~look at the bits~ , and that's lehmer's (not constant-time-able) method, or you do not, and that's stein's or the division-powered one, and i suspect it can be proven that yer stuck with quadratic runtime if you dun look at the bits.

asciilifeform: bvt: from surface look, loox like lulzy piece, e.g. 'The algorithm is not constant-time as shown but can be made constant-time with low overhead'

asciilifeform: bvt: the only new instrs that seem to be even theoretically of use, are 'mulx' and 'adcx' -- but i dun have any iron that supports these atm, and cannot even begin to say whether constant time etc

asciilifeform: mircea_popescu: this is why i like 'run 9000 shots, and discard outliers' (granted this only applies when the item is expected to go in constant time, goes without saying)

asciilifeform: BingoBoingo: in http://qntra.net/2019/01/constant-time-miller-rabin-test-added-to-finite-field-arithmetic/ , plox s/informating/informing

asciilifeform: in other lullies, https://duckduckgo.com/?q=miller+rabin+constant+time << seems like we're the only folx who ever showed detectable symptom of giving a shit..

asciilifeform: ( this is not a contradiction in terms, it is possible to implement whole thing, with same constant-time algos, by hand asm )

asciilifeform: ( and defo not in constant time )

asciilifeform: i prolly oughta add to the http://btcbase.org/log/2019-01-20#1888508 thing : 1 of the items which seemed like a speedup, but in actual practice sucked, was the use of (constant-time) 2 (ditto 4) -bit windows for modexp ( iirc apeloyee suggested ) ☝︎

asciilifeform: ( the 64x64 iron multer in amd/intel, possibly surprisingly, is in fact constant time, in all boxes i've tested to date )

asciilifeform: mircea_popescu: it is conceivable that the ones currently sold are constant time , i simply haven't tried'em.

asciilifeform: mircea_popescu: that wouldn't be constant-time...

asciilifeform: this allows 'P' to be a constant-spacetime operation, and hands the decision of 'just how important to constant-time the whole prime generation' to the author of the tape.

asciilifeform: which means ugh, for e.g. 2048bit candidate being tested for primality in constant time, ~each~ witness needs 1 modexp and 2047 modsquares !

asciilifeform: http://p.bvulpes.com/pastes/TkmoM/?raw=true << sneak peek of constant-time stein. ( afaik there isn't one anywhere else on the net, funnily enuff. )

asciilifeform: if primality test ( which consists of GCD ~and~ m-r, in order to constant-time ) does not exceed 0.0356sec, then on machine with 1 FG it can be considered that the FG is the limiting reactant.

asciilifeform: in other noose, constant-time stein-gcd aint so bad, 1msec (2048bit operands) , 6msec (4096bit) , 21msec (8192bit), 81msec (16384bit) ☟︎

asciilifeform: it is interesting to note, i did an exhaustive dig re gcd algos; and found that there are half a dozen sub-quadratic ones, but none of those can be made constant-time.

asciilifeform: otherwise can wait for asciilifeform's constant-time m-r ( or not, depending on what's in eulora war room chalkboard, i cannot presume to know what the priority is )

asciilifeform: ( in orig timeline also did not include problem of constant-time keccak, which i presently do not have, and neither anyone else, but is necessary to fill mircea_popescu's spec for the final product )

asciilifeform: i've actually found decent (not constant time, but didn't need, it only checked sigs) rsatrons in malware samples -- kB or so of asm. it aint exactly mystery, how to bake

asciilifeform: mircea_popescu: i didnt try patching out the test ( given as it's got montgomery, the answer will be soup ) but did try for odd exp, got ~same~ as for the nonconstanttime gmp knob ( which is pretty hilarious, means that they dun do anything differently for 'constant time' variant, evidently )

asciilifeform: http://btcbase.org/log/2018-12-18#1881465 << will add to this : on any hypothetical iron where add and sub aint constant-time ( i know of none , but could hypothetically exist in fyooyoor ) the overall 'is modexp constant-time' litmus will ring alarm. ☝︎

asciilifeform: at 1 time, was used in the constant entry ( nibble inserter ) routine, then the latter was replaced with rewritten http://www.loper-os.org/pub/ffa/hypertext/ch13/fz_io__adb.htm#29_14 , nao sole remaining use is in the knuth divider.

asciilifeform: ( the only guarantee i can offer in good conscience is that nuffin can be broken by operating the ~external~ controls -- but even there user is required to see whether his cpu has barrel shifter (see ch13 discussion) , constant-time mul ( see ch9 discussion ) )

asciilifeform: ( bonus is that the ~output printing~ itself is constant-time, ha )

asciilifeform realized that he's gonna need a constant-time keccak for the final chapters, dun have 1 yet

asciilifeform: the other is that on iron such as certain ARM ( i have not yet investigated ~which~ ) , and ppc, and certain others, there does not even exist a constant-time MUL, and one is stuck with some variant of http://www.loper-os.org/pub/ffa/hypertext/ch11/w_mul__adb.htm#33_13 -- which really begs to be asmed, is riotously inefficient

asciilifeform: ( bake it in ECL, then get 'for phree' not only constant-time, but constant-current.

asciilifeform: diana_coman: unlike, e.g., haskellists, we only do things if they make sense : as you pointed out, 'bit-vectorized' keccak aint constant time, no matter what, so no particular reason to bother with the massage

asciilifeform: ( if, btw, somebody else has the time/inclination to do the latter, i'll only say 'thx'. thing is already in xor-sat form, roll the constant term into the eqn's, set $known-schedule as the output values, and gaussian-reduce... )

asciilifeform: ( bonus is that the closed form is not only constant time, but substantially faster on pc, nomoar branch prediction misses ) ☟︎☟︎

asciilifeform: ( the table variant is elementarily not constant time on pc )

asciilifeform: http://btcbase.org/log/2018-10-12#1860789 << imho a ~constant time~ crc32 would be useful, and can be made from ave1's with very small effort, but i'ma leave it as exercise for him ( simply dispose of the if's ) ☝︎☟︎

asciilifeform: http://btcbase.org/log/2018-10-12#1860778 << there are not so many legitimate uses for /dev/urandom. however the idea that it can be fully reproduced in userland without kernel knob is afaik a mistake -- the thing gives you real entropy if available, and elsewise prngolade; importantly, as a ~nonblocking~ operation. idea is that it ~always~ returns in constant time. ☝︎☟︎

asciilifeform: !#s constant time

asciilifeform: ( recall, this was the orig thrust behind constant-time rsa )

asciilifeform: i find it hilarious how they carry on pretending that a crypto lib where ~some~ of the functions are (supposedly..) constant-time, is worth half a shit

asciilifeform: 'BN_gcd gets called to check that _e_ and _p-1_ are relatively prime. This function is not constant time, and leaks critical GCD state leading to information on _p_.' and a few moar.

asciilifeform: in other lullies, https://eprint.iacr.org/2018/367 >> 'Most of OpenSSL's constant-time code paths are driven by cryptosystem implementations enabling a dedicated flag at runtime. This process is perilous, with several examples emerging in the past few years of the flag either not being set or software defects directly mishandling the flag...' 'granularity issues due to word-size operands to the GCD function' etc

asciilifeform: it is demonstrably not constant time, on several popular machines, we went over this

asciilifeform: i'm curious, for instance, whether any of the cryptographers observed that the arithmetical routines behind your ecc are not in fact constant time on e.g. arm.

asciilifeform: zx2c4: i've spent the past ~2yrs writing a properly constant-time arithmetic lib. it is being slowly published. ( see earlier link to my www )

asciilifeform: btw zx2c4 , i must regret to inform you that the code you linked, is in fact NOT constant-time on several common architectures, because it makes use of machine MUL instruction ( gcc will compile a nonconstant-operanded '*' to e.g. IMUL on x86 )

asciilifeform: in other quasi-noose, if n is p*q, and 4p-1 = d*b^2, where b is integer and d is in {3,11,19,43,67,163}, n is factorable in polynomial time (with modest constant!)

asciilifeform: phf: phunphakt : ppc is one of the two currently-produced archs ( the other being arm ) that doesn't have constant-time MUL .

asciilifeform: ffa for instance is result of 'why not see what constant-time costs'

asciilifeform: (i.e. you don't need a universal shift register, can make 'constant' value using a just-in-time-cooked bitstream loaded in for that particular occasion)

asciilifeform: because the game board setup, if you will, also gotta be constant-time.

asciilifeform: somehow the 'i dug up an algo, by apparently sane author, and determined that it runs in constant time' -- not work ?

asciilifeform: mircea_popescu: all blockciphers are pseudoscientific. the only differences you can take to the bank, is that camellia was approved by nato bureaucrats, serpent was not; and the fact that serpent runs in constant time ( branch-free ).

asciilifeform: this is why ultimately entire primality test algo must be constant time, just like the other pieces.

asciilifeform: that ain't constant time !!

asciilifeform: other thing is that i dun see how this is constant time