#secp256k1

/

      • jtimon has quit
      • TD-Linux
      • gmaxwell
        TD-Linux: interesting! what is on input3?
      • TD-Linux
        gmaxwell, just a LED for triggering
      • gmaxwell
        thats great. so when the signing starts the led goes low?
      • TD-Linux
        yes
      • given that I have 4 channels, I can annotate this in much greater detail
      • gmaxwell
        there is a very clear power signature.
      • TD-Linux
        timing wise it's rock stable
      • gmaxwell
        TD-Linux: the '1 signing' is a zoom into the 10? looks like the patten repeats.
      • TD-Linux
        yes
      • the right bit is the next signature
      • with no delay
      • er actually not quite... the part on the right is serialize_compact I believe
      • gmaxwell
        looks like in the major operation there are 64 pulses, that would be the 64 table lookups and adds, from the 4-bit table usage.
      • so it looks like sha256 for RFC6719 I'd guess, then the generation of the nonce.
      • TD-Linux
        yeah, I can put additional annotations around any particular function
      • it's more interesting live... the "dip" in power at the very first of the 64 pulses is all over the place
      • but the rest are continuous
      • it's currently signing random data... I'm going to now apply patterns
      • gmaxwell
        The major secret operation is the same as generating a public key.
      • yea, it would be interesting to measure if the power signature of twice with the same nonce (resp. two public key generations with the same secret) are more correlated than ones with different secrets, and if so by how much.
      • TD-Linux
        yeah okay so with a locked message it's a lot more stable. it's very content dependent.
      • gmaxwell
        I wonder if that power dip is a cache miss when going to the table?
      • TD-Linux
        I'll need to check if I have caching on
      • gmaxwell
        a prefetcher probably hides the table accesses, esp since it reads 16 entries does some caculations then 16 more.
      • but it wouldn't hide the first one.
      • TD-Linux: how does the probing for this work?
      • TD-Linux
        we only care about key bits and not msg bits correct?
      • gmaxwell, it's a remade amplifier board with 1 ohm resistor across the power line
      • gmaxwell
        TD-Linux: yea, the attack you do to compromise signing is that you read off bits from the nonce.
      • if you can learn k you can recover the private key from the resulting signature.
      • TD-Linux
        I was able to see a less high quality but otherwise quite similar output just from the power rail.
      • alright let's see if I can extract 1 bit of information just visually
      • gmaxwell
        keep in mind that the table entries are in 64 16 entry tables, which are accessed in a way that should make them constant time, but perhaps not constant power. (and, in fact, looks to me that those spikes are pretty nicely consistently timed).
      • You can simplify your attack by generating a compressed public key, since that will do all the same operations, but let you set the bits going into it more directly. uh also the operations are blinded.
      • you might want to disable that for the moment. The blinding takes the key you've input (or the nonce) and adds it with some random number stored in the context, and adjusts the sequence of operations so that the initial value of the addition includes the negative of this number to cancel it out. If you're not calling the reblind call, that blinding factor is a constant, so it doesn't really add much
      • in the way of security... but it may make your analysis confused.
      • commenting out the call to secp256k1_ecmult_gen_blind in the ecmult_gen_create will turn that off.
      • TD-Linux
        yup can definitely extract 1 bit of information visually
      • gmaxwell
        oh yea?
      • TD-Linux
        well maybe not one bit
      • gmaxwell
        hah.
      • TD-Linux
        I can make two messages, store one as ref, and identify on the scope
      • gmaxwell
        will the scope helpfully align a stored trace on the trigger for you?
      • TD-Linux
        yes
      • gmaxwell
        sweet.
      • TD-Linux
      • gmaxwell
        these are certantly much cleaner than the stuff you recorded before.
      • TD-Linux
        yeah I haven't piped this to the lfrx yet though I certainly can
      • and yeah to be clear here the constant timeness is perfect, to the cycle.
      • gmaxwell
        yea, though I wonder if the phase of the operations changes. e.g. our constant time moves might consume more power earlier or later depending on which table entry they read.
      • on those zooms, where is that zoomed in? in the nonce generation in the middle somewhere?
      • indutny
        TD-Linux: awesome work!
      • TD-Linux
        gmaxwell, that's near the beginning of the 64 cycles.
      • there's a bit before that that's also key dependent
      • gmaxwell
        TD-Linux: but this trace I see, this is one of the 64 things? --- I think the flat top is the table access, it seems to do 16 things, and if so then the dip down after is the point addition. if so, thats a little sad, because that is a really big power signature difference at the end of it.
      • TD-Linux drops out serialization too as it's not relevant
      • TD-Linux
        gmaxwell, well we can get an answer to this real quick.
      • which function should I annotate on another channel? :)
      • gmaxwell
        you could put a led pulse in secp256k1_ecmult_gen right before ge_from_storage perhaps?
      • TD-Linux
        sure
      • gmaxwell
        or maybe turn on the led before the storage cmov loop and turn it off after?
      • we have a candidate patch that changes how the cmov works that might make its power signature less, so it would be good to try to just do that measurement right now.
      • TD-Linux
      • gmaxwell
        oh interesting!
      • TD-Linux
        also compare these two very first cmov loops with 2 messages
      • *keys
      • gmaxwell
        so it was the cmov loop that had the strong sidechannel.
      • thats good news.
      • I think the first cmov loop is suffering a cache miss.
      • or something?
      • TD-Linux
        indeed, the timing doesn't change though
      • gmaxwell
        that is strange. hm.
      • I don't get it.
      • TD-Linux
        are there any degenerate keys? like if key = 0
      • (this is literally key 0 and 1)
      • gmaxwell
        key = 0 is not valid (it produces the point at infinity which cannot be seralized)
      • TD-Linux
        okay let me change that.
      • I'll set the high bit as well.
      • gmaxwell
        how are you setting key 0? it should get rejected.
      • are you just timing a secp256k1_ecmult_gen directly?
      • have you disabled the blinding? the values are randomized.
      • TD-Linux
        yes blinding is off
      • and I'm calling the high level sign function
      • also I can come up with other key values that do the same thing I just showed so that's not related
      • (for some values the difference is smaller)
      • gmaxwell
        if (!overflow && !secp256k1_scalar_is_zero(&sec)) {
      • TD-Linux
        it is really weird because the *exact same* table values are iterated over in both cases, righT?
      • gmaxwell
        ^ _sign should reject a sec key of zero, and do so in a very not constant time way.
      • TD-Linux: well the way the cmov works is that it does bit masking, where the same table entries are read, and the one we want gets anded with 1s or 0s then ored into the target buffer.
      • TD-Linux
        ... oh lol my key is stack allocated and I didn't zero everything.
      • gmaxwell
        I suggest you change to using secp256k1_ec_pubkey_create as it will let you directly change the secret value that you're working with, and has a lot less garbabe that can't leak secrets.
      • All secp256k1_ec_pubkey_create does is takes your input, calls mulgen on it and seralizes the result.
      • TD-Linux
        does it still have the nonce stuff
      • (because that's also leaking, although less)
      • gmaxwell
        no, it's effectively just ecmultgen. but the signature process is k = hash(secret || message) then R = kG (exmultgen) then s = (secret * r + m) * (1/k) then it serializes r,s.
      • TD-Linux: if you're looking to bisect for other leak sources, all that after setting the k happens in secp256k1_ecdsa_sig_sign if you're saying there is a leak _before_ the secp256k1_ecmult_gen that would have to be in the RFC6979 hash... which seems pretty hopeless/unlikely?
      • TD-Linux
        yeah I think I'll look at that one later
      • first I want to figure out what's up with the cmov loop
      • gmaxwell
        well if you use the pubkey create you can access the input to that cmov directly, esp with blinding off. I think an interesting key set to look at would be 0xFF 0x00 ... x ... 0x00 0x00 with dots willed in with zeros and x filled in with the numbers 0-15
      • er 0xFF 0x00 ... x 0x00 0x00
      • so you'll have a bunch of constant cmovs, then one that varries with the key, then 16 cmovs that are constant.
      • or something like that, you should be able to look at the one that varries and see if the 16 different values leave obviously different power signature.s
      • the reason I keep suggesting pubkey create is because that gives you direct control of the cmov loop... while signing only lets you give different hash inputs to it.
      • (unless you replace the nonce function point with one that outputs what you want... which you can do too, but simpler to just use the pubkey create function.)
      • TD-Linux
        gmaxwell, okay so I swapped for pubkey create
      • arubi joined the channel
      • the huge initial cmov thing is totally gone
      • now I can set individual bytes in the key, and see them show up in the corresponding cmov
      • (first byte is second last cmov)
      • gmaxwell
        'huge initial cmov thing is gone' hm. that seems suspect to me.
      • TD-Linux
        yes same
      • here's a pic of the super professional setup https://people.xiph.org/~tdaede/pics/sidechanne...
      • jtimon joined the channel
      • gmaxwell
        TD-Linux: what amplifier is that?
      • TD-Linux
        AD8132
      • set for 10x gain
      • I have a couple others I could try as well
      • using a 1x probe because the output impedance is quite low
      • gmaxwell
        signal looks more than clean enough. probably bigger improvements would come from sheielding the setup, and using a test board with less unrelated junk that might be making noise.
      • TD-Linux: what clockrate are you running at?
      • TD-Linux: it would be interesting to try to characterize the CPU's impulse response. E.g. do a bust of heavy arithemetic, then go into whatever nop loop should use the least power. ( asm("wfi") ? ) I wonder if you get a similar delay as we see during the cmov?
      • s/delay/decay/
      • e.g. the current may be dropping in that exponential shape due to internal capacitance filling up during a time of lower load.
      • hm. but it's too slow to be capaitance. Perhaps some kind of dynamic voltage control inside the cpu that cuts things back when the cpu is doing boring stuff like the cmov.
      • jtimon has quit
      • jtimon joined the channel
      • jtimon has quit
      • jtimon joined the channel
      • instagibbs_ has quit