isis agora lovecruft (they/them) on Twitter: "this amusingly means that i will hold the title for implementing both the fastest and slowest elliptic curve related cryptographic implementations in the world 🏆🏆"

Country	Code	For customers of
United States	40404	(any)
Canada	21212	(any)
United Kingdom	86444	Vodafone, Orange, 3, O2
Brazil	40404	Nextel, TIM
Haiti	40404	Digicel, Voila
Ireland	51210	Vodafone, O2
India	53000	Bharti Airtel, Videocon, Reliance
Indonesia	89887	AXIS, 3, Telkomsel, Indosat, XL Axiata
Italy	4880804	Wind
3424486444	Vodafone
» See SMS short codes for other countries

isis agora lovecruft (they/them)‏ @isislovecruft 1h1 hour ago

in cryptography we assume some things about the hardware, usually including that it uses two's complement and has a constant-time hardware multiply instruction

1 reply 0 retweets 18 likes

Show this thread

isis agora lovecruft (they/them)‏ @isislovecruft 1h1 hour ago

so for example crypto on older macs with powerpc chips is "not possible" (not without a lot of effort) because the chip's multiplication instruction first looks to see if either multiplicand is 0 or 1, in which case it short circuits and returns 0 or the other multiplicand rsp

2 replies 1 retweet 13 likes

Show this thread

isis agora lovecruft (they/them)‏ @isislovecruft 1h1 hour ago

similarly also for ARM cortex-M3 chips, the multiply instruction can take 1-2 cycles less if both multiplicands are ≤ 2^16, either multiplicand is 0, or—somewhat strangely—either multiplicand is a power of two

1 reply 0 retweets 9 likes

Show this thread

isis agora lovecruft (they/them)‏ @isislovecruft 1h1 hour ago

of course there's ways around non-constant-time multiply instructions, like the well-documented tricks @BearSSLNews uses (cf. https://www.bearssl.org/ctmul.html or below) but afaik all them rely on tricking *some* form of a hardware multiply instruction into good behaviourpic.twitter.com/wDV8N6nUSU

1 reply 0 retweets 14 likes

Show this thread

isis agora lovecruft (they/them)‏ @isislovecruft 1h1 hour ago

in my quest to make commodore 64s secure against attackers with quantum computers by implementing supersingular isogeny key encapsulation in 6510 assembly, i obviously need constant-time multiplication, but forget even variable-time IT DOES'T HAVE *ANY* MULTIPLICATION INSTRUCTION

2 replies 4 retweets 38 likes

Show this thread

isis agora lovecruft (they/them)‏ @isislovecruft 1h1 hour ago

before jumping into the assembly (THERE WAS A JOKE THERE, DID YOU SEE, DID YOU SEE IT) maybe i should first show some C taken from an older version of BoringSSL which multiplies two n-bit numbers into a 2n-bit result in constant-time (albeit relying on hardware multiplication)pic.twitter.com/VwLCU6cDrC

a screenshot of this function from this commit in boringssl: https://boringssl.googlesource.com/boringssl/+/07432f325d6a388fe6d4881e84b076610c961f05/third_party/sike/asm/fp_generic.c#18

1 reply 0 retweets 27 likes

Show this thread

isis agora lovecruft (they/them)‏ @isislovecruft 1h1 hour ago

here's a fairly "simple" variable-time 8-bit x 8-bit -> 16-bit multiplication algorithm in 6502/6510 assembly, which indexes over the bits of the b multiplicand and conditionally either doubles or add-then-doubles, taking 146 cycles (best case) to 184 cycles (worst case)pic.twitter.com/Nh3hoONQRF

LDA #0 ; Initialize RESULT to 0
LDX #8 ; There are 8 bits in a
.do_add_then_mul:
LSR .b ; Get low bit of b
BCC .do_mul ; 0 or 1?
CLC ; If 1, add a
ADC .a
.do_mul:
ROR A ; "Stairstep" shift (catching carry from add)
ROR .c
DEX
BNE .do_add_then_mul
STA .c+1

4 replies 1 retweet 14 likes

Show this thread

isis agora lovecruft (they/them)‏ @isislovecruft 1h1 hour ago

here's the same routine made constant time by always adding-then-doubling which requires 283 instructions AND TAKES 374 CYCLES JUST TO MULTIPLY TWO BYTESpic.twitter.com/TBV7N5mlUh

a pile of horrible assembly so terrible that you really don't want to hear it but if you do it's over here https://github.com/isislovecruft/iso64/blob/master/src/c64/subtle.asm

1 reply 0 retweets 19 likes

Show this thread

isis agora lovecruft (they/them)‏ @isislovecruft 58m58 minutes ago

the 6510 chips in commodore 64s run at ~1MHz depending on whether it's the PAL or NTSC version, and a field element in this 434-bit prime field takes 56 bytes, so multiplying two field elements takes roughly 20,944 cycles or ~21ms assuming page boundaries aren't crossed

2 replies 1 retweet 11 likes

Show this thread

isis agora lovecruft (they/them)‏ @isislovecruft 53m53 minutes ago

i'm not sure how many field element operations i'm going to need to walk the isogeny graph yet, but i feel pretty confident that this is going to be the slowest post-quantum cryptographic implementation in existence, and quite possibly just straight up slowest crypto in the world

1 reply 2 retweets 21 likes

Show this thread

isis agora lovecruft (they/them)‏ @isislovecruft 53m53 minutes ago

this amusingly means that i will hold the title for implementing both the fastest and slowest elliptic curve related cryptographic implementations in the world