Score:2

Crypto

Is the following derived MAC where the output is XOR'ed with the key secure?

Doron Bruder

10/29/22, 4:06 PM

Hey I'm wondering if the following scheme is secure or not , I tried reductions and some tries to prove that it not must be secure but I feel completely stuck .

More details:
It's just any reduction that came to my mind (up to my knowledge) required knowing $k$ . I tried to use the 'classic' technique of trying to simulate somehow the original Mac and get into a contradiction of it being insecure itself (which is known to be secure in this question)

$\forall k\in\{0,1\}^{n},m\in\mathbb{M}$ $Mac_{k}^{'}(m)$ is defined as follows: $Mac_{k}^{'}(m)=Mac_{k}(m) \oplus k$ it's known that $Mac_{k}$ is secure note: $\mathbb{M}$ is the message space and it's assumed that the key $k$ is generated by some $\operatorname{Gen}$ algorithm in a random manner. It is asked to prove or disprove that $Mac_{k}^{'}(m)$ is necessarily secure.

137

0 + 11

encryption

mac

symmetric

authenticated-encryption

pseudo-random-function

Maarten Bodewes

10/30/22, 7:37 AM

"it is asked" and "not homework" are at odds to each other, Doron. The initial question even had a copy of the assignment. I removed the latter statement that it is not homework. The way it is asked the community should at least treat it as such.

SEJPM

10/30/22, 10:48 AM

Hint: Can you imagine a MAC which is by itself secure (though perhaps a bit "artificial") that would leak the key when used in this construction?

Doron Bruder

10/30/22, 6:52 PM

@SEJPM Iv'e tried for all day long with no success . Are u sure such construction exist ?

SEJPM

10/30/22, 7:33 PM

@DoronBruder the example you described in a previous edit + comment did work. I'm not sure why you think otherwise now?

Doron Bruder

10/30/22, 8:57 PM

@SEJPM it does not work as this way I could only reveal half of the key which alone does not finish the proof . I got really stuck there

SEJPM

11/1/22, 8:14 AM

@DoronBruder Hint: if you want to leak the entire key, can you somehow exploit the abilitiy to make multiple queries?

Doron Bruder

11/1/22, 2:01 PM

@SEJPM nope , not really , at least not with the construction I tried before . As adding 0^n/2 instead of half of the output or anything to one of the half sides will only discover half of the key ... note that both functions are from {0,1}^n to {0,1}^n

SEJPM

11/1/22, 2:02 PM

Well, can you perhaps move the zeroes around based on the queries?

Doron Bruder

11/1/22, 3:00 PM

I think I can! add zeros in either sides based on the m (inputs), when it's enough to add zero the one of the sides only for specific m and otherwise add zero the second side

Maarten Bodewes

11/1/22, 3:01 PM

You just beat me by a few seconds :) I think that's enough hints? Note that you could also switch based on the resulting MAC value although that's slightly more tricky. Also note that revealing even part of the key means that the algorithm is not as secure as it is supposed to be - leaking half of the key is enough to consider it broken.

fgrieu

11/1/22, 7:51 PM

Side but related remark: if $P$ is a random-like public permutation of $\{0,1\}^n$, efficiently computable in both directions, what can you say about $k\in\{0,1\}^n$ given $P(k)\oplus k$?

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is the following derived MAC where the output is XOR'ed with the key secure?

TH: MAC ที่ได้รับต่อไปนี้ซึ่งเอาต์พุตเป็น XOR'ed ด้วยคีย์นั้นปลอดภัยหรือไม่

RO: Este următorul MAC derivat în care ieșirea este XOR cu cheia securizată?

RU: Является ли следующий производный MAC-адрес, в котором выходные данные подвергаются операции XOR с ключом, защищены?

VI: MAC có nguồn gốc sau đây có đầu ra được XOR'ed với khóa an toàn không?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.