The Side Channel

forest

03:19

I wonder, why is padding used with RSA when it's being used to transmit a symmetric key which is already a blob of random data? It seems like padding is intended when the plaintext can be anything (e.g. could be very small or could be chosen by an attacker), which isn't really ever the case.

Ella Rose

03:40

@forest This is why using "public-key encryption" can be kind of silly (unless you want it to have homomorphic properties). Otherwise, just doing key encapsulation and hybrid encryption is almost always what public key encryption was going to be used for anyways, and solves some problems like the input to the public key operation needing to be randomized

If you're just sending a fully random block of bits, you don't need to pad anything

forest

@EllaRose That's what I thought. So why do key exchange protocols use padding?

Ella Rose

I'm not sure, it may have to do with a "key" only being a max of 256-bits, yet the block size being significantly larger

although of course, you could just as easily send a fully random block of bits over and hash it to obtain the key material

forest

But then the padding could just be purely random and only the last 256 bits could be taken as the key, or send a random blob and derive the key with a hash.

Ella Rose

I don't know which protocols you're referring to, and I wouldn't be that familiar with their guts even if I did

forest

TLS, OpenPGP, SSH, all the usual ones.

Ella Rose

03:45

using RSA (I assume) for key encapsulation is kind of silly anyways, if (EC)DH is available

forest

True, but in some situations like OpenPGP, it's needed.

Ella Rose

@forest you might ask this Q on the main site

forest

Or at least it makes sense.

@EllaRose Well I imagine the reason is historical anyway, so I didn't want to ask something that might be off-topic. Would it be appropriate on the main site?

Ella Rose

I can't imagine how it wouldn't be, even if that is the answer

forest

hmm alright

3

Q: Is semantic security important in a hybrid cryptosystem?

RSA doesn't provide semantic security when used unmodified, and neither does the commonly used PKCS#1 v.1.5 padding scheme for encryption. Is this a problem for hybrid cryptosystems at all? My suspicion is that it isn't, since the plaintext message of the RSA encryption should be a random strin...

@EllaRose Looks like someone already asked in 2013!

Ella Rose

03:59

Not surprising, though I'm not sure it answers "why not just send a n-bit random block"; For instance, the second comment deals with a 128-bit key, which obviously needs to be padded to the block size.

A 128-bit key padded with random data to the n-bit (e.g. 4096) block size for RSA would appear to be no different than a random 4096-bit block of data

forest

I imagine it's since you'd have to send out-of-band information to specify how the key should be derived and what size it should be, which isn't necessary with padding.

Ella Rose

I know OAEP is more complicated than just appending random bits though so maybe that has something to do with it

well, that could/should be specified by the protocol

rather than some kind of per-use out-of-band information

just hardcode the protocol to always hash the entire thing to compute the key or whatnot

Maeher

07:31

Generically using just a TDP instead of a CPA secure PKE can definitely be insecure if you're not careful about how you extract the key.

The output of a TDP can leak significant information about it's input without being broken.

So if you just use 256 bits of the 4096 bit preimage you would need to prove that those are actually hardcore predicates of the TDP.

A randomness extractor may be able to remidy that, but the whole thing just becomes a lot more brittle than just using CPA secure PKE.

( though it's been several hours, so maybe @forest no longer cares :D)

forest

Nah I just found another answer here:

6

A: Is RSA padding needed for single recipient, one-time, unique random message?

One thing you can do in this scenario, if you really don't want to use padding, is to use key encapsulation (RSA-KEM) instead. That is, instead of first generating a random AES key and then padding it to the full RSA message length, you instead generate a random RSA plaintext and then derive you...

What I described is apparently RSA-KEM, which does use textbook RSA.

@Maeher And yeah it looks like brittleness is the main reason.

And it's not like padding is expensive in the first place.

Maeher

08:11

Yes, as I said you can do it if you're very careful how you extract the key. Because leakage of information from the TDP is not *just* a theoretical concern. The RSA-TDP for example *does* leak information, specifically it leaks at least the Jacobi Symbol of the preimage.

So when Ilmari so nonchalantly says that you need to use a "suitable KDF" what that means is that you need to make damn sure that you use a good randomness extractor, that can deal with the leakage. (Of course what people are going to do is throw a hash function at it and pretend that it's a random oracle, which negates p…

Meta Crypto SE

1

Q: Are questions asking what [crypto term] is and used for on-topic?

The question What is a Pedersen commitment? was closed as off-topic, with justification that is is a "Requests for literature, software or similar recommendations", when I do not see that it is. I understand that perhaps we want to exclude overly basic/vague/broad questions like "what is a bit?"...

discussion

Maeher

08:42

It's kind of funny that "What are Pedersen commitments?" was closed but "What do curly brackets mean?" by the same author wasn't.

Luc

09:02

does it make a difference to cast only 2 votes instead of 3? Like, if I don't want two of the four to be elected but there is clearly a third and fourth choice for me, does it make sense not to cast a third vote or is that pointless?

(Two and thirteen comments, both over seven years, is quite a bit too little to be considered a moderator imo.)

SEJPM

@Luc essentially I'd think this means should the need for the 3rd preference arise you're giving both a 50-50

but as SE uses STV I suppose you could figure it out yourself ;)

Single transferable vote

The single transferable vote (STV) is a voting system designed to achieve proportional representation through ranked voting in multi-seat organizations or constituencies (voting districts). Under STV, an elector (voter) has a single vote that is initially allocated to their most preferred candidate. Votes are totalled and a quota (the number of votes required to win a seat) derived. If their candidate achieves quota, he/she is elected and in some STV systems any surplus vote is transferred to other candidates in proportion to the voters' stated preferences. If more candidates than seats remain...

(there are also some nice explanative videos of this on youtube)

Luc

I don't understand the algo at first glance (I saw the link on the election page) and am at work so I shouldn't spend the time to go through the calculations for a few scenarios, figured someone might know

but others might consider my third choice a first or second choice, so even if there is no need to determine a 3rd preference, my third choice will be taken into account. So it should be the case that not voting for third is more favorable for my first and second choice, right?

SEJPM

09:17

@Luc My understanding is that the way it works is that if your first choice guaranteed makes / doesn't make it only then your second choice becomes relevant

likewise with the second and third

so having a third shouldn't hurt your first two

Luc

ah I see what you mean now, that makes sense

Maeher

Apparently this election is surprisingly complicated. What I don't really get is what the "Primary" is supposed to be.

SEJPM

@Maeher it's meant for larger sites

so if we had >10 candidates there would be an additional week of "primaries" where you'd get to up- and down-vote on candidates

Luc

note the info box on the right hand side of that page

SEJPM

and the 10 with the best score would advance to the final phase (where we are right now)

Maeher

09:34

Ah, I thought the Primary was currently ongoing.

Maarten Bodewes

Heh, 10 candidates, we should be so lucky :)

Maeher

I still don't quite get how that voting system works. Since we have two positions to fill, it seems like I should be able to cast two "first choice" votes...

Maarten Bodewes

@forest Not quite. RSA KEM requires you to generate an integer in the range [0, N) - limiting it to [2^256, 2^(n -1)) could make sense - and then perform key derivation. That's not entirely the same as generating a number [0, 2^256) and using it directly as a key.

Maeher

Because apparently if my first choice gets the most votes, I have no say in who gets to be second, which seems rather weird.

M'vy

10:00

STV is basically, you count all the first choices. You remove the person with less votes. The people who voted for the eliminated person have they second vote becoming their new first vote. And you repeat again until there's only one person left (or as much as needed)

forest

@MaartenBodewes Yeah that's what I meant, using a blob and deriving a key from it.

Maeher

But *how* you derive it, is key. *rimshot*

I'll see myself out.

@M'vy That seems like weird way of voting when there are two positions to fill, because my vote can only ever support one candidate, even though there are two positions... maybe I'm thinking about this wrong.

M'vy

I'd need to review the process used in SE elections, but there are variations

Like with quotas to get elected. And once you get that quota, you transfer the rest of the votes too

the 'quota' being half the votes + 1

Maeher

It's very well possible that it's a lot more well thought out than it appears to me. (Though it was devised by the Stackexchange people... so who know.)

They thought the new "design" makes sense, so I wouldn't really trust their judgement.

M'vy

I think the Meek STV computes the fraction of your vote that allowed for the candidate to be elected, and transfers the other fraction to your next choice

Maeher

10:14

That... is a lot more complicated than I thought, yes.

But they use "opavote" which is great, I guess I'll get a new grandfather soon.

M'vy

like if you need 11 votes to get elected, and the candidate got 15 out of a total of 20 votes, it means that each 15 voters contributed 11/15th for this candidate. The 4/15th left are then attributed toward the tally for the second seat

Maeher

Yes, that actually deals with the problem that you would be throwing most of your vote away by having the most popular candidate as your first choice.

M'vy

mhmm

Maeher

Which in itself is a hilarious reversal of the problem of FPTP voting.

M'vy

reversal?

Maeher

10:21

in FPTP voting any vote for an unpopular candidate is basically thrown away. If you would only transfer the votes if your first choice does NOT get the most votes, then a large fraction of votes for a very popular candidate are essentially thrown away.

M'vy

ah right

Ella Rose

16:43

@kelalaka is there another comment that says the same thing and uses the "correct" formulation?

kelalaka

I don't remember but the accepted answer's first paragraph was same, in short. But does it matter?

Ella Rose

If the information is already present then I could see it as not being unethical - comments are supposed to be used to ask for information or to clarify information, so if the information is already present somewhere then the comment is not really necessary.

Different sites have different behaviors towards comments - they are supposed to be kept really clean and on the point of asking for clarification, but frequently mods just don't have enough time to always ensure that this is the case, and this tends to get worse for the more active sites

like questions on stackoverflow can have monstrous and huge comment threads containing comments that are explicitly not supposed to be there e.g. "+1 thanks!" because there is just too much content for the mods to keep up with

kelalaka

But at least, he can not downvote all the votes :)

Ella Rose

17:00

I have sometimes wondered what the comment landscape would look like if comments could be downvoted

kelalaka

+1

I need your advice. Should I turn back to write articles?

Ella Rose

What do you mean?

kelalaka

I had to left writing articles, it is almost two years now. I can turn back to it, or choose another path for my future which is not about academics...

I've unfinished articles waiting for me, even new ideas...

Ella Rose

17:15

articles about what? I'm not sure I am the right person to give you advice, that might depend on a lot of things, e.g. what you want from your life, how you're doing financially and how it will provide for you, etc

kelalaka

Cryptography of course. I cannot go to a conference, that is one of the issues.

b degnan

@kelalaka There's value in writing articles; however, I've found that in cryptography, it's really weird culturally compared to physics/quantum mechanics as they seem to be into legacy and family. Ella had a really good paper on a trapdoor that was rejected as they said "get a cryptographer". You don't have to go to a conference to have an impact.

kelalaka

I know this issue, In Euro Crypt 2008, one person published a graph for the authors in the Rump session. I was an interesting result that he said it is good to have x,y,z to have a co-author.

If I remember correctly it was about all 4 IACR conferences

b degnan

17:32

I wrote one paper that was outright rejected by IACR, but then used the same paper to get grant money. It's mostly who you know in cryptography is seems.

kelalaka

Even once saw that one professor talks about If we gave him x, then our paper will be accepted by seeing some side information, I guess. AFAIK, it may not be possible anymore.

b degnan

@kelalaka btw, if you ever want someone to read your papers, send it to me. I spend most of my time reviewing and writing papers. Unlike most people in cryptography, I'm easy to find due to my academic appointments.

@EllaRose Did you ever update that trapdoor paper? I still feel that should see publication.

kelalaka

@bdegnan thanks. Sure.

Future Security

19:17

I decided to spend a few minutes looking at password hashing again. I wanted to look for an overview of client-side (browser, not a system where salt doesn't need to be transmitted) password stretching. It's annoying that my searches keep coming up only with answers like "Don't hash passwords client-side. It's no more secure than sending the plaintext password."

That's just such a basic concept but isn't what I'm looking for at all. No, I'm not going to use unencrypted HTTP. No, I am going to have the client only load first party JS authenticated with TLS. No, I'm not trying to obfuscate or encrypt a password.

kelalaka

If the protocol simply hash and send, it is true, right?

Future Security

If it's plain salted or unsalted SHA, MD5, whatever then that's all true. But I mean something like Argon2 or bcrypt.

I'm not a fan of mandating the use of javascript at all, but I want to know if we can offload the work of password stretching from the server to the client.

That eliminates the problem of DOS via password hashing, forces online crackers to do the extra work instead of the server, and works around the problem of figuring out how much CPU time and RAM to reserve for password stretching.

You know how people have proposed requiring proof of work as a counter to spam and automated attacks? That's what I want to know more about for password hashing. With server-side hashing the server does a huge amount of work to test one password and the client does almost nothing. Instead I want the server to only require a small amount of work to verify and require the client do the big amount of work.

kelalaka

I see your point.

Future Security

19:35

It's not a huge challenge to hashing client side, but I want to know about how to handle salts. Do you make it site_wide_salt || email_address? Or do you do a database look up? If you store salts in a database then how do you prevent attackers from using salt requests to figure out who has or doesn't have an account on your website? And what about changing salts when changing passwords? Is it a big deal if someone probing your website can tell when someone has changed their password?

SEJPM

@FutureSecurity ideally you do what OPAQUE does and evaluate an OPRF

Future Security

Can you actually use a salt to prevent pre-calculation with that though?

SEJPM

@FutureSecurity using the OPAQUE OPRF the salt only depends on a per-user server-side static secret as well as on the password

so if you guess the wrong password you get the wrong salt

and if the user doesn't exist, a random server-side key should be used (IIRC)

(or some hash or something)

(lemme check)

Future Security

You're right about using a server side key to derive fake salts for missing users. The drawback is then that an attacker can tell when someone who (hasn't yet registers) registers an account on your service. Because instead of sending a random fake salt you send a real random stored salt.

I haven't yet done serious reading on OPAQUE but it's on my to-do list.

I think if you did passowrd-strech-then-verify then offline cracking will be defended against, but then you have the same salt-revealing and/or precomputing problem.
And if you do verify-then-strech then once your verifier database gets leaked then efficient offline cracking becomes possible, I think.

SEJPM

hmm, looks like I can't find the behavior of OPAQUE in case of an invalid username

Future Security

19:54

I remember Matthew Green saying something like "The salt never leaves the server side and the password never leaves the client" to describe OPAQUE. (Which sounds really cool.) He's also got a long blog post related to the same subject which I haven't read yet.

SEJPM

@FutureSecurity tools.ietf.org/html/draft-krawczyk-cfrg-opaque-00#section-5

^ there's a dedicated section in the OPAQUE draft to user enumeration attacks

apparently the idea is to pick the server-side key always as "PRF(master_key, user_name)"

and also apparently to avoid the encryption of the DH keys leaking user existence

you derive another key from the encryption key for that one and have the server know it

the client can then re-do the derivation upon login

Now the server can send a (randomized!) encryption of the ciphertext blob to the client

and whenever the username didn't exist, it simply encrypts an appropriate amount of zeroes

SEJPM

20:19

@FutureSecurity so I thought about it a bit more and it should be easy to extend OPAQUE to work on top of TLS and only provide a yes / no answer for whether a shared secret was agreed upon

Now the truly interesting question would be whether one could skip some of the KE exponentations in OPAQUE if one is only interesting in whether or not the value is shared

(while still allowing for no more than 3 message exchanges)

SEJPM

20:43

0

Q: Can "OPAQUE-over-TLS" authentication be optimized?

So while discussing the issues of password-hashing off-loading in our chat I noticed that it's easy to extend OPAQUE (CFRG draft) to essentially be a better standard password based authentication when executed over TLS. Namely one could simply append a message $F_K(2)$ (for some pre-defined PRF $...

authentication tls passwords pake

^ @FutureSecurity you gave me this idea, thanks!

Ella Rose

21:13

@bdegnan No, but i did use a modified version of it for the underhanded crypto contest, which got my name mentioned at DEF CON: youtube.com/…

b degnan

22:14

@EllaRose That's almost as good as a publication. :)

Transcript for