log☇︎
211 entries in 0.732s
asciilifeform: ( and still not constant time )
asciilifeform: eagle eyes, apeloyee . i dun suppose you have a constant time gcd up your sleeve ?
asciilifeform: in other noose, asciilifeform derived a simple constant-time variant of barrett. short enough to put in the l0gz:
a111: Logged on 2017-09-20 02:01 asciilifeform: in other noose, asciilifeform found that 1) knuthian division can be sped up by ANOTHER factor of 2, by walking the bits of the quotient instead of shifting'em 2) barrett reduction in constant time is almost certainly possible
a111: Logged on 2017-09-30 18:26 asciilifeform: the continuing lulzy part is how everywhere on the net you will find 'constant time crypto libs are available', 'it's a solved problem', 'this reduction routine is constant time', and all of it is liquishit and doesn't stand up to 30 seconds of examination with naked eye
asciilifeform: the continuing lulzy part is how everywhere on the net you will find 'constant time crypto libs are available', 'it's a solved problem', 'this reduction routine is constant time', and all of it is liquishit and doesn't stand up to 30 seconds of examination with naked eye ☟︎
asciilifeform: author ~does~ have some strange cockroaches in his head: cites shamir's 'proof that factoring can be O(log N)' but omits to mention that it requires a machine that works in arbitrarily-sized integers in constant time...
asciilifeform: in other noose, asciilifeform found that 1) knuthian division can be sped up by ANOTHER factor of 2, by walking the bits of the quotient instead of shifting'em 2) barrett reduction in constant time is almost certainly possible ☟︎
asciilifeform: http://btcbase.org/log/2017-09-17#1715294 << computing an 'unchanged' TAKES SAME TIME as any other, omfg, it's constant time ☝︎
asciilifeform: in other olds , https://archive.is/ksYSr << DIV instruction on recent intel, NOT constant-time
a111: Logged on 2017-09-13 17:17 asciilifeform: apeloyee: anything that beats multiply-then-divide is an improvement, so long as it meets the basic demands ( constant time, constant space, NO branches that depend on input bits, no use of approximations, no massively heavy - 100 loc is a good approx max - code )
asciilifeform: if you made the double-wide reciprocal ( i will leave aside the question of how to do this in provable constant time and provable correctness ) you're stuck using that width.
asciilifeform: apeloyee: anything that beats multiply-then-divide is an improvement, so long as it meets the basic demands ( constant time, constant space, NO branches that depend on input bits, no use of approximations, no massively heavy - 100 loc is a good approx max - code ) ☟︎
a111: Logged on 2017-09-12 23:12 mircea_popescu: and finally 3. the item there described is not exactly a function. it rather something i'd call a mechanism, a discrete item that does a fully defined thing. as we're looking more and more through ada eyes and constant time things and so on, a study of these mechanisms as an distinct category will prolly be useful. somewhere between conway's cells and commandline utils, they are.
mircea_popescu: and finally 3. the item there described is not exactly a function. it rather something i'd call a mechanism, a discrete item that does a fully defined thing. as we're looking more and more through ada eyes and constant time things and so on, a study of these mechanisms as an distinct category will prolly be useful. somewhere between conway's cells and commandline utils, they are. ☟︎
asciilifeform: it requires a constant-time gcd, however, to be constant-time. ( and has a problem same as above in that it takes much MORE time than naive algo if you don't reuse modulus forever )
mircea_popescu: if you want constant time, you feed the list 9, 0,0,0,0,8,0,0,1. it will do 18, 1, 18, 1, 18, 1, 18, 1 etc.
mircea_popescu: will necessarily have the modulus of the sum. this entire procedure is constant time.
mircea_popescu: you write by hand a function which takes a list with a promise none of the items on it exceed a mod, and returns the mod of the sum of the sum of the elements, in constant time.
mircea_popescu: that small cost can be slightly higher and constant time.
asciilifeform: valentinbuza: i regard the entire concept of 'real time automated public key crypto' as a scam, and anyone claiming to offer such a thing, as a scammer, until constant time rsa routines are public.
asciilifeform: incidentally all existing systems that do pubkey crypto in real time ( incl. 'noise' ) are trivially breakable by the enemy, because no constant-time numeric stack currently exists publicly.
asciilifeform: ( for reference : leaking 1/4 of your privkey is fatal; 10-20% -- you're breakable in polynomial time with large -- how large is unknown -- constant factor )
a111: Logged on 2017-08-15 22:52 mircea_popescu: constant-time MPFHF is now an open question for teh interested.
mircea_popescu: constant-time MPFHF is now an open question for teh interested. ☟︎
mircea_popescu: the ONE way to constant-mpfhf is to calculate ALL the tree of possibilities, 2^message length items EVERY TIME
asciilifeform: ALL ffa ops take time that is not dependent on the hamming weight. that's what 'constant time' means.
asciilifeform still devising a constant time gcd
asciilifeform: the other thing, you don't need ANY trial-divisions in the prelude to miller-rabin, IF you have a constant-time gcd
asciilifeform: while we're on the subj of 'cryptographers' : a constant time gcd is also apparently not known.
mircea_popescu: asciilifeform amusingly, the guy complains about the modular exponentiation not being constant time. maybe write to him ask where he ever saw a sane algo ?
asciilifeform: meanwhile from literature search, every article ever, apparently, written re 'constant time modular exponentiation' proposes... tables
asciilifeform: ( thing still runs in constant time: N always walks the range of 1 to last digit of the width of our ffa )
asciilifeform: i understand what is meant by 'prototype', but an rsatron (ignoring for a moment the constant-time thing) that uses fermat's primality test as the sole probe, is analogous to a grenade with a half second fuse
asciilifeform: 'femaleworry' is idiotic because it's a decision algo that dun converge in constant time
mircea_popescu: sina you mean, is there a side channel for constant time ops ? or for rsa as commonly implemented atm ?
asciilifeform: mod6: other thing, since ffa is constant time, your N! is in O(N) (if mul were considered a constant op and brought outside of the brackets. which is is, 10! with 4096bit ffa, takes exactly C longer than 9! with 4096bit ffa. etc )
mircea_popescu: this would be automatic-constant-time cpu, run any software you want.
sina: if you impl as constant time you don't need ctgrind
sina: asciilifeform: btw I was going to ask you about your feelings on this https://github.com/cforler/Ada-Crypto-Library ...obviously hasn't been impl for constant time/space but regardless. may be possible to ctgrind it using that valgrind patch I linked in the logs
mircea_popescu: basically the other side of the "constant time" coin is that... YOU GET CONSTANTTIME, BITCH.
a111: Logged on 2017-06-27 00:57 asciilifeform: sina: one of the things gossipd needs is a constant-time-constant-space rsa. if you don't have one, enemy can derive your privkeys remotely based on timing.
asciilifeform: and the way to provably do this, is method called 'constant time arithmetic'
asciilifeform: sina: making 'constant time rsa' by trying to bury the rsa in a fixed 'box' of time, only works if you can guarantee LOWER bound of how long the rsa ops (ALL of them, till the end of time) take, as well as UPPER
asciilifeform: and the only way to make it so that i can't -- and ~probably~ so -- is to do your arithmetic in constant time.
asciilifeform: the only way to make guaranteed time bound is... constant-time arithmetic
sina: ok fair point, I get the general need for constant time constant space algo regardless of gossipd stuff anyway
asciilifeform: sina: one of the things gossipd needs is a constant-time-constant-space rsa. if you don't have one, enemy can derive your privkeys remotely based on timing. ☟︎
asciilifeform: STILL NOT IN CONSTANT TIME because apparently mother dropped him as a child
mircea_popescu: this then reduces to the case where constant, space, time etc
ben_vulpes: do forgive my ignorance, but why must rsa ops run in constant, worst-case time?
asciilifeform: 0 way to guarantee constant-time-anything
asciilifeform: http://btcbase.org/log/2017-06-12#1669058 >> this is a lulzgem, 'I also tested BN_mod_exp_mont_consttime from OpenSSL since that's a large function which calls functions from several other files. It turns out not to be constant time! There's a secret dependent memory access...' ☝︎
sina: (Checking that functions are constant time with Valgrind)
asciilifeform: compared performance of 'kindergarten' multiplier ( halfword at a time, uses machine's MUL instr. which apparently IS constant-time on x86 (but NOT on arm! would need test routine at warmup to establish if can use MUL ) )
asciilifeform is haunted by the notion that constant-time karatsuba gotta exist SOMEWHERE
asciilifeform: that's what constant-time means.
asciilifeform: in fact, it is well-known not to be constant time on recent intels.
asciilifeform: that there is NO guarantee that MUL/IMUL (or equiv. on other cpu) is constant time !!
asciilifeform: nao we need a non-recursive (! , SPARK won't allow recursion nor is it constanttimesafe to have any), constant-time karatsuba...
asciilifeform: basic principle of constant-time proggy
asciilifeform: only constant-time shift-and-subtract division
asciilifeform: 0 useful docs anywhere on division in constant time
asciilifeform: gotta have the constant-time exponentiator .
asciilifeform: also irritating is the fact that, while we have constant-time routines, it is impossible to guarantee constant-current (yes)
asciilifeform: for my purposes i could entirely do with a constant-time-and-space mult algo that knows when to set the overflow flag.
Framedragger: i mean, 'compared to what'. certainly not compared to asciilifeform's actually-fucking-constant-time crypto architecture
asciilifeform: does anybody have a favourite constant-time modular-exp ??
asciilifeform: ^ with constant-time mul
asciilifeform: phf: http://wotpaste.cascadianhacker.com/pastes/z16GS/?raw=true << tentative constant-time >wordsize-increment shifters.
asciilifeform: thing is optimized for -- strictly -- constant (always-worst-case) time and space usage; and fits-in-head (in that order)
asciilifeform: e.g. that it is possible to operate on a thing of bitcoin's complexity, in constant space AND time
Framedragger: (okay apparently if your cpu supports 'constant_tsc' (as seen in cpuinfo) then this timestamp counter actually counts time and not processor ticks which is a *good thing* given freq scaling etc.; this is available in all new intel processors; what a rabbit hole, man)
asciilifeform: 'When Intel first invented the TSC it measured CPU cycles. Due to various power management features "cycles per second" is not constant; so TSC was originally good for measuring the performance of code (and bad for measuring time passed). For better or worse; back then CPUs didn't really have too much power management, often CPUs ran at a fixed "cycles per second" anyway. ...'
asciilifeform: sl/include/polarssl/ssl.h is extended to include the session _checksum, tool_id, use_custom, and xor_key. The data contained within this packet is constant with the exception of a time stamp taken from the real-time clock and a few bytes of random data. A CRC checksum is computed from the entire packet and is included with the HELLO packet. When Blot receives this packet, it checks the CRC searches a list of previously seen packets f
asciilifeform: where, yes, you can add 0xFFF......FFF and 1 in constant time, but the cost is that now some numbers are 'special'
asciilifeform: 'The signing function in crypto/ecdsa/ecdsa_ossl.c in certain OpenSSL versions and forks is vulnerable to timing attacks when signing with the standardized elliptic curve P-256 despite featuring constant-time curve operations and modular inversion. A software defect omits setting the BN_FLG_CONSTTIME flag for nonces, failing to take a secure code path in the BN_mod_inverse method and therefore resulting in a cache-timing attack vulne
pete_dushenski: ben_vulpes: beeping and flashing orange dash light every time traction control activates, which in rwd car with 275 rear section tires on freshly snowed roads is... constant.
Framedragger: quite sure the diff'ing / updates were thought out thoroughly, i.e. time complexity is constant.
mircea_popescu: http://btcbase.org/log/2016-10-19#1556736 << the lulz of all time being the "price" and "market cap" as reported by you know, "Exchanges" where this shitstain "is traded" being CONSTANT in the interval. ☝︎
Framedragger: asciilifeform: re. "Enemy can spam the channel but each of his packets can be rejected in ~constant time~" - ahh! that clarifies matters for me. will comment on blog later by PC. ttyl
asciilifeform: and there are no sybils, even as a theoretical item, in a correct gossiptron - every receiver knows exactly who (pubkey-wise) has any business transmitting to it, and rejects packet that is malformed, replayed, or signed with ANY other key, in constant time.
asciilifeform: the only permissible operation on an unsigverified input is - constant-time sig verification.
asciilifeform: isn't it a constant-time op ?
asciilifeform: factorable in ~constant time.
assbot: CacheBleed: A Timing Attack on OpenSSL Constant Time RSA ... ( http://bit.ly/1VOQ9sc )
ben_vulpes: phf: i tried for a very long time with erc in a seperate emacs instance running on a server as a bouncer, and the *constant* muscle memory confusion over the subtle differences between emacs-in-terminal and emacs-with-gui drove me up a wall
asciilifeform: oh one other thing, blocks really ought to live on a storage device where connecting tx outputs is a constant-time operation.
asciilifeform: #6508 61457c2 Switch to a constant-space Merkle root/branch algorithm. << anybody have the time/energy to look? i don't...
assbot: Logged on 03-01-2016 03:56:57; BingoBoingo: <pete_dushenski> last time i tried it was >1gb of ram, so the footprint's coming down. << Ironically my bastart build went from consistent ~300 MB to constant 1 GB of RAM after BDB fix
BingoBoingo: <pete_dushenski> last time i tried it was >1gb of ram, so the footprint's coming down. << Ironically my bastart build went from consistent ~300 MB to constant 1 GB of RAM after BDB fix ☟︎
mircea_popescu: neither my e nor my planck constant have "declined" over time.
nubbins`: "The need to assemble is as constant among humans as the necessity of making decisions is rare. Assembling corresponds to the joy of feeling a common power. Decisions are vital only in emergency situations, where the exercise of democracy is already compromised. The rest of the time, “the democratic character of decision making” is only a problem for the fanatics of process. It’s not a matter of critiquing assemblies or abandoning them,
Adlai: (this seems to be djb's real reason behind discounting curves without a *convenient* constant-time algorithm)
Adlai: re: montgomery ladder, you can implement constant-time secp256k1, but it's a pita
adlai: well anyone can factor a number of arbitrary length in arbitrary time... consistently being able to factor arbitrary length numbers in constant time, now that is a 'supernatural' algorithm, relative to current knowledge
BingoBoingo: spring operated wrist mounted time standard is only 1.5 minutes off of ntp reported time in 8 years of constant operation.
BingoBoingo: Let time stay constant. If planetary rotation slows acknowledge that as the problem.
mircea_popescu: What if the terrorists hear about fast secure crypto? Yikes! Similar to constant-time story. Don’t standardize good crypto. Discourage use of good crypto. If the good crypto persists, try to bury it behind a huge menu of bad options. Advertise “cryptographic agility”; actually cryptographic fragility. Pretend that this “agility” justifies using breakable crypto.
pete_dushenski: asciilifeform: 'time was flowing at a constant rate of one second per second!'