Computer Science

Ran G.

12:01 AM

@Gilles they are not useless, they prevent MITM. however, there is no reason to send R_A in the clear

it wasn't clear to me if <x,y,z> is equivalent to <x,<y,z>>. I guess not by your definition that n is encoded as well

Gilles

@RanG What could Trudy do if the first two messages were omitted?

Ran G.

which brings me to conclusion that it is secure: only Alice generates enc of e(<>,K) where the <> has 3 arguments, and everytime she does so, the third argument is P_A

Gilles

I'm uncomfortable with B not providing his own nonce

@RanG <x,y,z> != <x,<y,z>>. It's an unambiguous encoding. X.509 or whatever. For the purpose of this question, the internal content of the messages has an unambiguously parsable structure

Ran G.

@Gilles it was important in the original scheme, without the payload. Now the scheme is not really (identity) authentication but message-authentication

Gilles

@RanG authentication without a payload isn't very useful, which led me to want to add a payload in the first place

Raphael

12:07 AM

Hi guys

Gilles

all the original protocol could do is say “I'm alive”

Raphael

@Gilles Oh dear, @uli had some time to spend again.:D

CS Meta

1

Q: tag: cryptography vs security

The question Break an authentication protocol based on a pre-shared symmetric key was tagged with both cryptography and security. What is the difference between these tags, and when should each be used?

Ran G.

@Gilles so it's not very clear what the purpose is. Alice and Bob already share a secret Key. I thought this way Bob knows the message is from Alice by comaring the value R_A, since Eve can generate arbitrary message, that will decrypt to random value R_A..

BTW guys, isn't it the middle of the night your time? you seem to very active in the nights :)

Raphael

@Gilles your 3-SAT wiki is funny. The excerpt is longer than the main thing, and they are contradictory. I approved nevertheless, maybe you can check again.

Computer Science

12:14 AM

0

Q: Break an authentication protocol based on a pre-shared symmetric key, with message numbers

Consider the following protocol, meant to authenticate $A$ (Alice) to $B$ (Bob) and vice versa. $$ \begin{align*} A \to B: &\quad \text{“I'm Alice”}, R_A \\ B \to A: &\quad E(\langle 1, R_A\rangle, K) \\ A \to B: &\quad E(\langle 2, R_A+1, P_A\rangle, K) \\ \end{align*} $$...

cryptography protocols authentication

Gilles

@Raphael are they? You know this stuff better than me, can you fix it?

Raphael

you said "exactly 3 variables" in one, "at most 3" in the other

will do

Gilles

@Raphael blame @RanG for the excerpt and me for the main wiki

well, me too for the excerpt since I approved it

Do we want MathJax on Meta?

it would let us illustrate MathJax problems, have a sandbox, etc.

I think the other sites that have MathJax have it on meta as well

Ran G.

@Raphael exactly-3-sat is equivalent to upto-3-sat. when people say 3-sat they can mean whichever is more convinient, right?

Raphael

@Gilles I'd like that.

@RanG Yup. Therefore, I think the common definition is the more lenient one (Occam's razor ;)).

What did you think about meta.cs.stackexchange.com/q/145/98 ?

Ran G.

12:27 AM

@Raphael I fancy the CW solution, unless an answer already appears in TCS.SE, etc.

Gilles

@Raphael hate it, still on my to-answer list

give me 10-20min

Ran G.

Do you think we can urge the SE team to end the private beta and start the public one?

Raphael

12:55 AM

@RanG Don't know. I guess we fulfilled their requirements,though.

@Gilles you know that amortised and expected time are different things?

Gilles

@Raphael yeah, yeah, I'm on it

So is k-SAT “exactly k” or “at most k”?

all the articles I find define it as “exactly k”

Raphael

@Gilles "at most k" can always be made into "exactly k", so you use "at most k"

@Gilles Most proofs do because it is convenient

but as I said,it does not matter at all

For results, that is. Proofs become messy if you have (unnecessarily) many cases.

Gilles

@Raphael I was going to reject your excerpt edit, but someone already approved it

it needs to spell out what “3-KNF” means

Raphael

1:12 AM

@Gilles No,not in the excerpt,imho.

KNF is standard terminology. Those who do not know it should click through.

Gilles

@Raphael those who'll use the tag may not be very familiar with standard terminology

for example, most of my education was in French, and I later never had much to do with constraint programming. I didn't know the term KNF. I do know what satisfiability is, and conjunctive normal form.

Raphael

that aside,your edit is too long. look at the tag list

your edit is not helping. what is a "clause"?

the term does not make sense in general formulae.

you just need too much space for explaining 3KNF to a layman.

Gilles

@Raphael then propose something shorter

Raphael

I did.

Gilles

as long as it doesn't require knowledge of any abbreviation, it's fine by me

Raphael

1:17 AM

won't work. "A formulae of propositional logic in conjunctive normale form where each clause has at most three literals" -- that alone is as long as the excerpt should be

Gilles

How about: 3SAT is a satisfiability of propositional logic formulas in conjunctive normal form with up to 3 literals per clause. It is a famous NP-complete problem.

Raphael

I really think the excerpt should (only) be informative to most reasonably well-read, and potential pitfalls should be filled in the full wiki text. It can't be any other way.

Gilles

In fact it should be that way: the definition first, then the important property

@Raphael No. The excerpt is what you see when you decide whether to use a tag. It needs to be widely informative.

The excerpt doesn't have to have a full definition, it's ok that you can see what it's about

Including abbreviations in there raises more questions than it answers

Raphael

3KNF is maximum information in the space. Besides, anybody who should want to tag something "3-sat" should at least know KNF;forother cases,there are mods.

I have no problem at all with raised questions. It is a complex definition.

@Gilles I can agree with that.

by the way, not knowing english terms/abbreviations is a French problem to some extent. I expect most users who know their way around CS at all to be familiar with English terms.

Gilles

So how about: 3SAT is satisfiability of formulas in conjunctive normal form with 3 literals per clause. It is a famous NP-complete problem.

@Raphael not at the undergrad level, I think

Raphael

1:25 AM

I reject this proposal

we have to find something better

"is satisfiability" is weird on its own

Gilles

@Raphael what would you have? If someone doesn't know what satisfiability is, then they won't go looking for the tag anyway

Raphael

3SAT is an algorithmic decision problem. Satisfiability is an abstract property.

@Gilles I am not sure about German undergrads, but in general I guess most if not all text books are English. In know that in India all higher ed is in English.

@Gilles We will see how well we can deal with the programmer-CS language barrier. Me, I am certainly going to insist on some level of abstraction and precision in both answers and questions.We will see.

I guess a common problem will be people trying to ask stuff in CS lingo that end up asking something entirely different.

Raphael

2:30 AM

@Gilles I am putting together an aggregate answer for the book list question. However,because of multiple books per answer I am not always sure what to do.

Gilles

@Raphael put all the books you recommend in your answer. No more, no less.

If you think the guy should get X, Y and Z, then answer “X, Y and Z because …”

It doesn't matter if your list intersect with the one in another answer

Your answer is your list, not an item

Raphael

but in case of lists,would not per-item voting be superior? I think of it as "find the best pieces for a central list" rather than "find the best answer".

Gilles

@Raphael per-item voting does not work

If you want a poll, you have to start with all options present

and what you get is what's popular, not what's good

a book list is only worth asking for if you're putting your reputation behind your recommendation (your real-world reputation, not the SE number)

If you want to say a book is great, write a ***** review on amazon

Raphael

I don't understand what you are getting at.Of course it is about opinions which other up- or downvote.That's SE. Evidence is largely optional.
Even if the content itself is clear-cut correct (or wrong), votes will depend on your presentation and wether it matches the taste of many readers.

Arguably, the most popular books are in someway also the best.

(in science)

anyway, have to get some sleep.

Have a good night (and Sunday)!

Gilles

2:47 AM

CS: repeating SO's mistakes

which SO is still paying for

Shouldn't scientists understand about learning from experience?

Raphael

?

Maybe we need more to be swayed from our idealistic viewpoint than "Forget it, it does not work."