Possible to generate a one time secret which all nodes on the distributed network can know but cannot pre compute I have a distributed P2P network.

Everyday, I want each node to have a secret which is only valid for that day, while each of the other remaining nodes on the network will be able to calculate the same value.

However, I do not want any node to be able to precompute this; for example, if it is Monday I do not want any other node to be able to compute the secret until Thursday evening / Friday

Is this possible? What kind of scheme would be needed for this to be effective?

Edit - have to edit here as i do not have enough reputation to comment, thanks for the answers so far, it would be impossible for me to have a centralized server, as this would break my model, can we achieve this without the need of centralized servers, and as for my adversary model, currently i am assuming a network of 5,000 nodes, which anything up to 49% of computing power maybe comprised by an attacker, so a solution needs to take into account the computer power at the disposal of an attacker and cannot relay on it might take x days

Edit 2 - The network is not closed, and yes the secret would need to be known to all 5,000 + nodes, but only be able to be computed / distrubted on a specfic day and valid for that day, i have been looking at network voting systems, all nodes compute a hash based on the previous days hash (like the bitcoin hash challenge where the solution is a nonce when added to another hash has x amount of zeros first) and then the average or mean of these is the secret used for the next 24 hours

If you have the bandwidth to do so, and good communication reliability between the nodes, you can perform a multi-party Diffie Hellman key exchange. The most efficient way to do so would be using X25519, resulting in a shared 256-bit secret between all parties. This can then be used to derive keys and other secret values.

This would also allow new nodes to be added to the network at any time, their public key would be added to the pool and all parties would calculate a new shared secret from the current secret. Parties would have to agree on the time it takes to distribute and calculate the secret, and use that to agree on a set time when that secret would go into effect. If it takes approx 5 mins to distribute all the public keys, they may start communicating to the network 7 mins in advance so there will not be a blackout period where some nodes do not have the secret calculated.

Bandwidth can be reduced substantially if a node trusts other nodes to forward a public key to other nodes on their behalf, and computation can be reduced if a node trusts other nodes to compute an intermediate shared secret from the rest of the network.

A ring-bus design could also be used, where nodes transmit to a single peer, and they receive from a single peer, and transmit the pool they receive which grows by 1 with each transmission. At the end all nodes should have the same list, and they can verify a hash of the key pool with other nodes randomly. If a peer does not have the same hash, but does have all keys, they may have been given an intentionally incorrect key(s), and procedures can be put in place which allow groups of peers to determine where the incorrect key(s) originated (traitor tracing).

The most reliable option is to have a node send its public key to all peers in the network, and receive the keys from all other nodes as well, resulting in $n^2-n$ total key transmissions for $n$ peers, then validate the list with several other peers.

Another option is available if all nodes have a permanent shared secret, the network is open, and nodes can access the internet without restriction. A high entropy public value, such as the output of the NIST randomness beacon, can be processed with HMAC, using the permanent secret as the key. The resulting output would not be able to be generated in advance of the beacon, and will be cryptographically secure because of the generation method, as long as the secret remains isolated to the network.

A combination method can also be used, in advance of the beacon publication, all nodes use Diffie Hellman to agree on a shared key for processing the next days beacon, this gives plenty of time to verify that each node has the same key. This would be the best option for nodes on an open network with a wide range of distribution (high latency), or a very large number of total nodes.


Encrypt data. Create 5 keys. Just 3 keys are needed for decryption I would like to encrypt some data and create 5 keys. These keys are stored in different places. If I want to decrypt the data I just need 3 of these 5 keys.

Is there a way to do this?

Yes, there is.  And it generalizes easily to requiring any $k$ out of $n$ keys, not just 3 out of 5:

Generate a random key for some symmetric encryption scheme (say, AES-SIV).
Encrypt your data with that random key.
Use a threshold secret sharing scheme such as Shamir's secret sharing to split the random key into $n$ shares, such that any $k$ of them are needed to reconstruct the key.

You can use those $n$ shares directly as the $n$ "keys" to be stored in different places.  However, if you'd instead prefer to use $n$ pre-existing keys, you'll need one more step:

Encrypt each share with one of the $n$ keys (using whatever encryption scheme you prefer, either symmetric or asymmetric) and store the encrypted shares alongside the encrypted data from step 2.

To decrypt the data, do the same in reverse: first decrypt at least $k$ of the shares (if needed), then reconstruct the random key from those shares, and finally decrypt the data using the random key.

Shamir's secret sharing is unconditionally secure, so the whole scheme is as secure as the encryption schemes you use in steps 2 and (optionally) 4.


NIST's Public-Key Post-Quantum cryptographic public calling Is NIST's public calling:
https://csrc.nist.gov/news/2016/public-key-post-quantum-cryptographic-algorithms
...for a post-Quantum Cryptographic Algorithm a public calling for a public key distribution method (ex. Diffie Hellman) or a public key encryption method (ex. RSA)?

The second paragraph in the link you shared says the following:

  It is intended that the new public-key cryptography standards will specify one or more additional unclassified, publicly disclosed digital signature, public-key encryption, and key-establishment algorithms that are capable of protecting sensitive government information well into the foreseeable future, including after the advent of quantum computers.

So it appears that they want both key establishment algorithms (what you refer to as "public key distribution method") as well as public key encryption algorithms (and digital signature algorithms too).


Advantage of zero knowledge protocols So a zero knowledge protocol (ZKP) is a protocol for which there exists an algorithm, called the simulator, which can produce, upon input of the statement(s) to be proven, but without a witness for the truth of the statement, transcripts indistinguishable from those resulting from interaction with the real prover.

My question is this:

How is this good?

Indeed, one advantage is that the protocol leaks no information of the prover (I guess that's why it's called zero knowledge) since it produce what the prover would have produced without passing through him.

But, that exactly means that any can pretend to be the prover. Which isn't very good.

Am I getting something wrong?

Here's the example I use sometimes.

Suppose I want to convince you that I am an excellent archer.
If I show you a target painted on a wall, and an arrow in the bullseye of the target, are you convinced? No, since for all you know I could have fired the arrow first and then painted the target around it. In fact, even you could have done that, and you not a skilled archer. If instead you yourself paint the target first and watch me fire the arrow at the bullseye later, that's much more convincing.

So the "byproducts" of this interaction (the target and arrow) by themselves are not convincing. You could have generated them yourself (i.e., simulated them) even if you are an unskilled archer. Only if these byproducts were generated in a particular interactive way do they become convincing.


In TLS 1.3 handshake, what's "PSK binders" used for? PSK handhanke works like session ticket resumption in TLS 1.2, but I found a set of PSK binder for each identity(ticket) in TLS 1.3, why PSK binder are needed in TLS 1.3 ? To protect some attacks?

The current TLS 1.3 draft (-28) talks about the binder value:

  The PSK binder value forms a binding between a PSK and the current
  handshake, as well as between the session where the PSK was
  established and the current session.  This binding transitively
  includes the original handshake transcript, because that transcript
  is digested into the values which produce the Resumption Master
  Secret.  This requires that both the KDF used to produce the
  resumption master secret and the MAC used to compute the binder be
  collision resistant.  See Appendix E.1.1 for more on this.  Note: The
  binder does not cover the binder values from other PSKs, though they
  are included in the Finished MAC.

So the idea seems to be that the binder value can be used to somewhat "prove" to the server that the client knows the pre-shared key associated with a given identity (and it's the same the server remembers). This also ensures that they won't just go ahead and run a PSK handshake when they don't actually have a PSK.

Additionally it binds the previous session ('s handshake) to the current session ('s handshake) which could e.g. allow the server to discover that the client previously suffered from a MitM attack when the attacker forwarded the identifier but naturally got a different PSK on both ends and is gone for the session resumption.

To see the first property have a look at section 4.2.11.2 and section 7.1. In section 7.1 you see that the binder_key is rather immediately derived from the PSK. Now for session resumption the PSK is the resumption_master_secret. But more importantly section 4.2.11.2 tells us

  The PskBinderEntry is computed in the same way as the Finished
  message (Section 4.4.4) but with the BaseKey being the binder_key
  derived via the key schedule from the corresponding PSK which is
  being offered

and so knowledge of the binder key immediately implies knowledge of the PSK. And knowledge of the binder key is confirmed by verifying the bound message.


Is FFT for power-of-two cyclotomic rings possible if q is not 1 modulo 2n? For RLWE (Ring Learning With Errors) scheme, we use $R_{q} = \mathbb{Z}_{q}[x]/(x^{n} +1) = \mathbb{Z}_{q}[x]/(\Phi_{2n}(x))$ where $n = 2^{d}$ for some $d$. Since there exists $2n$-th root of unity in $\mathbb{Z}_{q}$ (which is the generator of the cyclic group $\mathbb{Z}_{q}^{\times}$), we can do FFT with the choice of the root of unity $\omega$ and do polynomial multiplication in $O(n\log n)$. Is there a way to apply FFT for primes $q \neq 1\,(\mathrm{mod}\,2n)$, so that there's no $2n$-th root of unity mod $q$?

Yes, in a way. When $q \neq 1 \mod 2n$ the ring $R_q$ is not fullt splitting (into polynomials of degree one). However, it might be splitting into several smaller polynomials of degree larger than one. Let $n > d > 1$ be powers of two such that $q$ is a prime and $q \equiv 1 + 2d \mod 4d$, then $X^n + 1$ splits into $d$ irreducible polynomials of the form $X^{n/d} + r_i$ modulo $q$ where $0 < r_i < q$ (see Corollary 1.2 in https://eprint.iacr.org/2017/523.pdf). Then you can use FFT to compute multiplication in $d$ levels, and then do it manually in the end. This can be as fast as full FFT (see e.g. https://eprint.iacr.org/2020/1397.pdf).


Mutual Index of Coincidence I can't seem to find a simple explanation of Mutual Index of Coincidence.

I am finding explanations of Mutual Index of Coincidence not Index of Coincidence.
I don't understand what the formula below means

$$\textit{MI}_c(\mathbf x, \mathbf y) = \frac{\sum_{i=0}^{25} f_i\times f'_i}{n\times m}$$

I want to write code to compute it.

As defined e.g. in Stinson's Cryptography: Theory and Practice (1995, 1st ed.; the earliest source for the term I could find that has even excerpts online), the mutual index of coincidence of two strings of symbols (letters, numbers, whatever) is simply the probability that two symbols chosen at random from each of the strings will be the same.

The formula you've quoted for calculating it looks somewhat garbled, though.  The original(?) definition given in Stinson's book looks like this:

  DEFINITION 1.8   Suppose $\mathbf x = x_1 x_2 \dots x_n$ and $\mathbf y = y_1 y_2 \dots y_{n'}$ are strings of $n$ and $n'$ alphabetic characters, respectively. The mutual index of coincidence of $\mathbf x$ and $\mathbf y$, denoted $\textit{MI}_C(\mathbf x, \mathbf y)$, is defined to be the probability that a random element of $\mathbf x$ is identical to a random element of $\mathbf y$. If we denote the frequencies of $A, B, C, \dots, Z$ in $\mathbf x$ and $\mathbf y$ by $f_0, f_1, \dots, f_{25}$ and $f'_0, f'_1, \dots, f'_{25}$, respectively, then $\textit{MI}_C(\mathbf x, \mathbf y)$ is seen to be $$\textit{MI}_C(\mathbf x, \mathbf y) = \frac{\sum_{i=0}^{25} f_i f'_i}{n n'}.$$

For example, assuming that $\textbf x = \text{"ABACA"}$ and $\textbf y = \text{"BABAA"}$, then $n = 5$, $f_0 = 3$, $f_1 = 1$ and $f_2 = 1$ (since $\textbf x$ contains five letters: three $A$'s, one $B$ and one $C$) while $n' = 5$, $f'_0 = 3$, $f'_1 = 2$ and $f'_3 = 0$ (since $\textbf y$ contains three $A$'s, two $B$'s and no $C$'s), so the mutual index of coincidence of $\textbf x$ and $\textbf y$ is $$\textit{MI}_C(\mathbf x, \mathbf y) = \frac{f_0 f'_0 + f_1 f'_1 + f_2 f'_2}{n n'} = \frac{3\times3 + 1\times2 + 1\times0}{5\times5} = \frac{11}{25} = 0.44.$$

In particular, note that the "plain" index of coincidence of a string of symbols, i.e. the probability that two symbols chosen at random from the same string are equal, is very close to the mutual index of coincidence of the string with itself.  The only difference is that the single-string definition assumes that the two symbols are always chosen from different positions in the string (i.e. that we never just pick the same position twice and compare the symbol there with itself), which requires a small correction.  That is to say, $$I_C(\mathbf x) = \frac{\sum_{i=0}^{25} f_i(f_i-1)}{n(n-1)} \ne \textit{MI}_C(\mathbf x, \mathbf x) = \frac{\sum_{i=0}^{25} f_i^2}{n^2},$$ but the difference between the two formulas approaches zero as the length $n$ of the string $\mathbf x$ increases (and, in practice, is small enough to get lost in random sampling noise anyway).

(Also worth noting is that there are some minor variations between authors in the definitions of both the single-string index of coincidence and the mutual version.  For example, Wikipedia — which currently doesn't mention the mutual index of coincidence at all — uses a definition of $I_C$ that differs from Stinson's by being multiplied by the alphabet size $c = 26$, ostensibly to make it more comparable between texts written in alphabets of different sizes.  In any case, such minor differences in definitions have no real effect on cryptanalysis.)

Anyway, what's this whole "mutual index of coincidence" good for, then?  Well, for one, given two strings sampled from the same plaintext source but encrypted with possibly different shift ciphers — such as two columns from a Vigenère ciphertext, after determining the key length $\ell$ and splitting the ciphertext into rows of $\ell$ characters — we can use it to determine whether or not the strings have been encrypted with the same shift amount.

By further shifting the characters in one of the strings by successive amounts, and finding the shift that maximizes the mutual index of coincidence, we can quite reliably determine the difference between the two key letters used to encrypt those columns.  In this way, once we've guessed one letter of a Vigenère key, we can statistically determine the rest of them, effectively reducing the Vigenère cipher to a simple monoalphabetic Caesar shift cipher.


Facebook app-scoped identifiers and similar - implementing stateless ID obfuscation After certain privacy concerns Facebook rolled out a bunch of changes to their APIs, one being "scoping" user identifiers per app. In effect, this means that Alice's canonical facebook user ID is never shared through facebook APIs, but each app sees a unique never-changing value.

To formalize this through two functions:

mask(user_id, app_id)
unmask(masked_id, app_id)

These functions should satisfy some properties:

reversible: user_id == unmask(mask(user_id, app_id), app_id)
secret: given y = mask(user_id, app_id) it should be 'hard' to obtain the original user_id.
deterministic: mask(user_id, app_id) == mask(user_id, app_id), where user_id == user_id and app_id == app_id
collision resistant: for all user ids, given the same app_id, it should not be the case that mask(user_id1, app_id) == mask(user_id2, app_id)

After a lot of reading, I have come up with two possible implementations:

Stateful: store a triple (user_id, app_id, hash(user_id, app_id)).
Stateless: for each app_id generate & store a secret, and encrypt(user_id, secret) on the fly. the encryption should be a deterministic cypher, such as AES-SIV.

From the get go, I'd like to avoid a stateful implementation. I am not sure however as to the validity of the stateless approach as I'm not very familiar with deterministic symmetric cyphers, and their security implications.

Is there some other approach I might be missing here? I think this is a deceptively easy problem, looking forward to get some insight.

Reversible implies collision-resistant, as you have defined it.  The criteria you have written down are essentially the criteria of deterministic encryption; if you add the criterion that it be hard for anyone without an app's key to forge a masked user id, then deterministic authenticated encryption[1] is exactly what you seem to be looking for.

If a user id is at most 64 bits, you could simply use AES itself as a deterministic authenticated cipher: $$\operatorname{mask}(\mathit{user\_id}, \mathit{app\_id}) := \operatorname{AES}_{k_{\mathit{app\_id}}}(0^{64} \mathbin\| \mathit{user\_id}).$$  The masked user id is 128 bits long.  If, on decryption, you verify that the upper 64 bits are all zero, what you get is a deterministic authenticated cipher with distinguishing and forgery advantage bounded by about $2^{-64}$.


What is the best algorithm for compressing a hash? What is the best way to transform a hash with a longer length into one with a smaller length, preventing as many collisions as possible? (Hashing the hash)

For example: Some versions of Git use SHA-1 for hashing commits. Of course, 15ce7ff90976b3e43738be403f5c985377646bb3 is rather large to display on a screen. Because of that, Github usually only shows the most significant 4 bytes (15ce7ff9) to refer to a specific commit.

But is this the best strategy or is there a better way? If SHA-256 was used instead of SHA-1, would the resulting "minified" hash be as secure and as colision-avoiding as possible within 4 bytes, regardless of the "minification" algorithm used?

What's better? Displaying more information than 4 bytes will be more secure mathematically speaking. However, it is unlikely that people will check all those bytes. Those bytes are more for identification than for authentication / security anyway. You could use a different alphabet than hexadecimals, say base 64, but I'd argue that that would be harder to remember, especially if more than 4 bytes are used.

For the 4 bytes it doesn't really matter. They only represent somewhat over 4 billion possibilities (using the short scale) and generating the same 4 bytes will be easy whatever hash function is used. The switch from SHA-1 to SHA-256 is about the full hash used internally.

The switch to SHA-2 is important in my opinion. Or it is at least important enough to make the switch. I haven't been swayed by Linus arguments yet, but that's mainly because I don't have a full overview of the vulnerabilities. However, I haven't seen a good argument why there wouldn't be an attack possible either. And the difference in speed really isn't worth to taking any risk.

A note about the wording: taking the first 4 bytes from a hash is not compression. Compression (as in the common meaning, such as the DEFLATE used by zip archives) is performed over all the bits, and tries to pertain some essential (or for lossless compression all of the) data. As explained in the comments below, compression of the output of a hash is an act of futility.

In cryptography compression has a different meaning. But the output must also depend on all the input bits.

Anyway, just removing the rightmost bytes from a hash is not the same thing.


Benchmark for CSPRNG as stream ciphers? My limitation in my security protocol is that I want my RNG as CSPRNG and I also want it to be super fast.
If I use Salsa20 or ChaCha or AES counter mode, I don't get the desired speed. I want my PRNG to work at the speed of 100 Gbps or more.
Morever, I need to be cryptographically secured.
Any suggestions regarding that? Do there exist such CSPRNG that can give me output stream at the speed of 100Gbps or above? Or in other words that can provide bit streams with a speed of 10^-11 bits per sec?
P.S: I don't care about the system requiremt, the platform could be FPGA, GPU etc, I just need some numbers to compare with and to know that with any kind of feasible platform (not super computers) can I achieve the target of 100Gbps in any of the CSPRNG?

The first thing to NOTE is that said by SEJPM in the comment, performance depends on the hardware - in both horizontal (core count, etc.) and vertical (clock speed, etc.) dimensions. The second thing to understand is that, although CSPRNGs and stream ciphers can share underlaying primitive, their security requirements are different.
So now, let's get started - what're some of the famous symmetric-key primitives?
There are 2 dimensions to consider when excluding the hardware parallism:

block size,

execution time per block.

Grades from slow to fast in: $$\text{Moderate} < \text{Fast} < \text{Very Fast} < \text{High} < \text{Very High}.$$ The grades are my personal opinion.

Primitive
Block Size
SW Performance Grading
HW Performance Grading

Gimli
384-bit
Very High
Very High

Keccak-p[1600,24]
1600-bit
Very Fast
High

Keccak-p[800,12] (not yet standardized)
800-bit
High
High

AES-128
128-bit
High
Very High

ChaCha20
512-bit
High
High

I haven't done systematic benchmarks on diverse hardwares and implementations yet, but the numbers are provided here for a quick reference. I used my own (hardly-optimized) MySuiteA library with ad-hoc benchmarking code written in a rush.

Primitive
Time of $2^{20}$ iterations of execution on Apple Silicon M1

Gimli
0.973sec

Keccak-p[1600,24]
16.495sec

Keccak-p[800,12] (not yet standardized)
8.143sec

AES-128
35.657sec(sw,unoptimized) 0.184sec(arm-neon-crypto)

ChaCha20
1.287sec

Next, we can consider implementation side.

SBox Modern cryptography wisdom says this: avoid SBox if it has to be implemented using look-up table (because it's a cache-memory side-channel), so AES is the most dangerous here;

Block Size AES is also dangerous due to its small block size - 128-bit is too small a space for nonce and counter. ChaCha20 also has only 128-bit space for nonce and counter, but it has larger state and a side-channel-resistant non-linear layer.

ARX vs Binary Polynomial ARX stands for Add-Rotate-Xor, which is a traditional paradigm for obtaining non-linearity (ChaCha20 follows this). It has the implementation disadvantage of requiring somewhat more complex circuit when doing a hardware implementation, and this is where ones without arithmetic addition - those based on binary polynomials have a win (Gimli, Keccak).

Word Length It was a surprise for me to see that my software AES implementation is actually very bad, but anyway, it's a byte-oriented algorithm anyway. What I want to note here is that, Keccak-p[800,12] out-performed Keccak-p[1600,24] not because of smaller block size, but because the fewer number of rounds - using 32-bit words on a 64-bit machine is actually a drawback when compared with using native word lengths. It is for this reason, SHA-512 outperforms SHA-256 on 64-bit computers.

Side information:
Gimli had a full-rounds distinguishing attack last year: https://eprint.iacr.org/2020/744 . Gimli isn't the only 384-bit permutation though, Xoodoo is also a good 384-bit permutation, and is authored by the same group of people invented Keccak, but I haven't implemented in my suite for benchmarking yet.


Is $H'(M) = 5M + 9H(M) \pmod{2^n}$ a secure hash function? theorem: For arbitrary $i≥0$ there exists $m,n≥0$ such that $35+i=5m+9n$.

We can use this theorem for constructing simple hash function.

Let $M$ be message and $H(M)$ be its hashed value with hash function such as the $\text{SHA}256$. We construct new $n$ bit hash function $H'$ as follow:

  $H'(M)=5M+9H(M) \pmod {2^n}$

Is this hash function safe?

Edit: I want use this to compress $H$. So suppose that $n$ is smaller than bit size of $H$.

Consider

$$H(M)= 9^{-1} (E(M) - 5M) \pmod {2^n}$$

where $E$ is encryption using a random permutation with an efficiently computable inverse $D$. This is a secure hash for the same reason the  Matyas–Meyer–Oseas construction is.

Now using your definition of $H'$ we obtain:

$$H'(M)=5M+9H(M) = 5M + (E(M) - 5M) = E(M) \pmod {2^n}$$

Thus $M = D(H'(M))$ can be recovered and $H'$ is not a secure hash for all secure hashes $H(M)$.


One Time Pad for large changing files i wondered what the security implications are if I do the following. If I had a large file encrypted with a OTP and want to change only a few bytes in the plaintext. what security vulnerabilities do I get if I only generate a new OTP for the changing bytes leave the old OTP as is and substitute the new OTP, and do this every time i make a change to the plaintext.

To be clear:

plaintext p;
OTP o;
cyphertext c

Start with…

p = 1111 1111 1111 1111
o = 0001 0001 0001 0001
c = 1110 1110 1110 1110

change plaintext…

p = 1111 1111 1111 __1010__

generate new OTP for the last 4 bit 0101 und substitute it in the "old" OTP…

o = 0001 0001 0001 __0101__
c = 1110 1110 1110 1111

What are the problems ( if there are any ) resulting from this?

I know that if I want to use OTP, I have to generate a hole new pad. But if I have a huge file (multiple GBs), it is hard to generate a new pad of this size if I only want to change a few bytes.

I haven't found material about this topic so far and analyzing attacks against some cypher application is a hard task, but maybe someone has read an article about that OTP application and why you should not do this.

If you only ever use a particular OTP block to encrypt one plaintext block, there is no way to decrypt it.

However, with your approach anyone looking at multiple versions of the file will be able to tell which parts have changed. For example, if the file contained secret messages stored by users, it would leak the length of each message added. Maybe that's a problem, maybe not. Depends on your application.


Schnorr identification protocol security proof I read about security proof of Schnorr identification protocol against impersonation attack. For the sake of comprehensibility let me sum up the protocol: Given group $G$ with generator $g$. Verifier is initialized by prover's public key $g^a$, where the knowledge of secret counterpart is to be proven by prover. The protocol runs as following:

Prover generates random $a_t\in G$ and sends $g^{a_t}$ to verifier
Verifier responds by sending random $c$ to the prover.
Prover responds by sending $a_z = a_t + c\,a$
Verifier checks whether $g^{a_z}\overset{?}{=}g^{a_t}\,(g^a)^c$

Now, the idea of the security proof was: Given adversary $\mathcal{A}$ being able to issue valid $a_z'$ against arbitrary public key $g^{a'}$, we can turn $\mathcal{A}$ into an efficient $\mathrm{DLog}\,_g(g^{a'})$ oracle.

The proof assumed we can "rewind" the adversary so that it issues 2 different $a_z$'s with respect to a single $a_t$. I didn't understand this assumption. It seems somehow incomplete to me. What if I have non-cooperative adversary? This can't be turned into DLog oracle, since such adversary were indistinguishable from honest prover who knows secret key, thus breaking zero-knowledge protocol property. So is this a complete proof, which I merely didn't get or is the fact that malicious adversary might break the protocol without breaking DLog on $G$ essentially unprovable?

It is important to understand that the simulator is a non-interactive machine; it does not interact with the prover (or with anybody else). What it can do is mimic (or simulate) a real interaction between the prover and the verifier, by playing the roles of both parties and internally "sending messages to itself". But it is not required to mimic the protocol exactly, only to produce an output that is close enough to the output of a real execution of the protocol. This is why it can internally repeat the protocol many times until it obtains a satisfactory output; there is no need for the prover to "cooperate", since again the simulator does not interact with the prover.


Mutual verification of shared secret Is it possible to develop a scheme where two parties, unsure if they have the same secret, can verify that the other does or does not share the same secret, without one party being able to cheat and come away with more knowledge than the other? (Or that if one does, that this can be detected by the other party.)

Let me explain using an example from our friends Alice and Bob. Their boss Charlie has just given Alice and Bob symmetric keys he requires them to use to communicate with him; $K_a$ and $K_b$, respectively. Alice and Bob expect their keys to be different, but are concerned that perhaps Charlie has reused the same key out of laziness.

Alice and Bob would like to verify each other's keys in such a way that, either:

They both come away certain that $K_a = K_b$; or
They both come away believing that $K_a \not= K_b$.

In other words, they want to prevent the possibility that:

One party can discover that $K_a = K_b$ but conceal this, so the other party comes away believing that $K_a \not= K_b$ and unaware that foul play has taken place.

Note: Let's assume here that Alice and Bob are communicating on a secure channel and have authenticated each other. Let $h()$ be a secure hash function.

A naive approach would be a scheme like:

---> Alice sends $h(h(K_a))$ to Bob
<--- Bob sends $h(K_b)$ to Alice

The problem here is that Bob could receive $h(h(K_a))$, calculate $h(h(K_b))$, discover they are equal but instead send $h(\textrm{random data})$. Alice might now believe her key is different to Bob's, when in fact he is able to decrypt all her messages.

I have tagged this with commitments since my guess is that the only way to solve this problem, if indeed it can be solved, would be for both Alice and Bob to both commit to something about the verification messages they are about to transmit, so that they cannot later change what they send without the other party realising. They might also be able to use some zero-knowledge proofs on each other, so I tagged that too.

Another idea I had was that Alice and Bob could reveal their keys one bit at a time through a commitment scheme. That is, each sends $h(\textrm{bit}_i||\textrm{nonce}_i)$ for each bit $i$ of their keys. They then take it in turns to reveal the nonces; as soon as there is a mismatch, they stop sending nonces. A cheating party learns at most a few bits more than the other (depending on how well they can guess bits), which is still not ideal, but I suppose it is better than one party learning everything.

By Theorem 3 on page 15 of this paper,
no secure-with-abort protocol for equality of long strings can be within 1/5 of fair.

If there is a protocol for equality on a domain of size at least 3 which is

secure against honest-but-curious adversaries, then oblivious transfer protocols exist.

If oblivious transfer protocols exist, then there are protocols for equality which give $P_1$

security-and-guaranteed-output-delivery and have $P_2\hspace{-0.03 in}$'s possible outputs be $\: \{\hspace{-0.02 in}\neq,\hspace{-0.03 in}\neq_{\hspace{-0.03 in}\perp},\hspace{-0.04 in}\perp,\hspace{-0.04 in}=\hspace{-0.02 in}\}$

and give $P_2$ the security that consists of indistinguishability from the ideal functionality

for which [if the inputs are equal then $P_2$ outputs the simulator's choice of $=$ or $\perp]$

and [if the inputs are not equal then the simulator chooses between $[P_2$ outputs $\neq]$

and $[P_2$ has a small chance of outputting $\perp$ and otherwise outputs $\neq_{\hspace{-0.03 in}\perp}\hspace{.02 in}]]$.

Such a protocol can be constructed as follows:

Start with Section 3.2, even though the domains are both super-polynomially large.

Look at $\operatorname{Sharegen}_r$, which is the box at the top of page 9.

If $\: x=y \:$ then set $\: \hspace{.03 in}j = i^* \:$, $\:$ else choose $\hspace{.03 in}j$ uniformly at random from $\: \{1,...,r\}\;$.

Ignore for loop immediately after $\operatorname{Sharegen}_r\hspace{-0.04 in}$'s choice of $i^*\hspace{-0.03 in}$.

Instead, this phase is to set $a_{i^*}$ and $b_j$ to the relation ($=$ or $\neq$) that holds between $x$ and $y$,

give $i^*$ and a share of $a_{i^*}$ to $P_1$, give $\hspace{.03 in}j$ and a share of $b_j$ to $P_2$, and give each of them $r$

real-or-simulated shares for the $a$s and $b\hspace{.02 in}$s in order to hide $i^*$ and $\hspace{.03 in}j$ from $P_2$ and $P_1$ respectively.

Note that either the integer prefixes must have the same length as each other

for the same party, or a stateful MAC must be used instead of concatenation.

Now, look at the box at the top of the next page, but ignore its step 3.

Just like that paper mentions on page 10 in the paragraph that starts with "Proof", the rest

of this paragraph will ignore the MACs and the fact that the parties are to be checking them.

If $P_1$ gets $P_2\hspace{-0.03 in}$'s share of $a_{i^*}$ and $a_{i^*}$ is $=$ then $P_1$ [outputs $=$, sends the next message,

and then halts]. $\:$ Otherwise, $P_1$ will output $\neq$ when $P_2$ aborts or the for loop reaches its end.

If $P_2$ gets $P_1\hspace{-0.04 in}$'s share of $b_j$ and $b_j$ is $=$ then $P_2$ outputs $=$ and halts. $\:$ If the for loop reaches its end

and $b_j$ is $\neq$ then $P_2$ outputs $\neq$. $\:$ If $P_2$ gets the simulated-share for $b_{j-1}$ but does not get

$P_1\hspace{-0.04 in}$'s share of $b_j$ then $P_2$ outputs $\perp$. $\:$ If $P_1$ aborts at any other time then $P_2$ outputs $\neq_{\hspace{-0.03 in}\perp}$.

Note that for an adversary, acting as either party, the ability to abort and get significant information about whether or not the other party got $\neq$ for [the $a$ or $b$ value which the honest party would learn if both parties were honest] would let the adversary significantly bias the other party's output.

(i.e., significantly beyond what can already be done in the ideal model)

.

For that construction, "a small chance" means "probability $1/r$".

Since it gives $P_1$ gets security-with-guaranteed-output-delivery, which is even stronger than security-with-fairness, the above protocol runs into the limits imposed by the impossibility proof. $\:$ On one hand, just ignoring the subscript on $\neq_{\hspace{-0.03 in}\perp}$ gives $P_2$ security-with-abort,

so doing that must come at the cost of significant unfairness.

On the other hand, doing that and replacing $\perp$ with $=$ gives $P_2$ approximate fairness,

so doing that must come at the cost of security-with-abort.

However, time-lock puzzles are enough to get around that, yielding a protocol such that

$P_1\hspace{-0.04 in}$'s possible outputs are $\: \{\hspace{-0.02 in}\neq,\hspace{-0.03 in}\neq_{\hspace{-0.03 in}\perp},\hspace{-0.03 in}=_{\hspace{-0.03 in}\perp},\hspace{-0.04 in}=\hspace{-0.02 in}\} \:$ and $P_2\hspace{-0.03 in}$'s possible outputs are $\: \{\hspace{-0.02 in}\neq,\hspace{-0.03 in}\neq_{\hspace{-0.03 in}\perp},\hspace{-0.03 in}\perp,\hspace{-0.03 in}=_{\hspace{-0.03 in}\perp},\hspace{-0.04 in}=\hspace{-0.02 in}\} \;$.

$P_1$ still gets security-and-guaranteed-output-delivery,

but that delivery will take time $T$ when $P_2$ aborts.

$P_2\hspace{-0.03 in}$'s standard-model security (i.e., what applies even if $P_1$ can quickly break the puzzles)

is like it was for the previous protocol, but if the inputs are equal then the simulator

can alternatively choose $=_{\hspace{-0.03 in}\perp}$. $\:$ If the puzzles are secure against $P_1$, then $P_1$ aborting

or not is statistically close to independent of $P_2\hspace{-0.03 in}$’s input and for equal inputs, the probability

of $P_2$ outputting $\perp$ is statistically close to $1/r$ times the probability of $P_1$ aborting.

.

Time-lock puzzles can be brought in to do that as follows:

The initialization phase will produce $\:a_1,...,a_r\:$,$\:$ rather than just $a_{i^*}$. $\;\;\;$ If the inputs are equal then for all elements $i$ of $\:\{i^*,...,r\}\:$,$\:$ $a_i$ will be $=$. $\;\;\;$ Other than that, the $a$s will all be $\neq$.

$P_1$ will get a share of each $a$, but $i^*$ is to stay hidden from $P_1$. $\:$ $P_2$ will get time-lock puzzles that encode shares of the $a$s, rather than real-or-simulated shares of not-necessarily-existing $a$s. $\:$ (Those shares will not need to be at-all hidden from $P_2$, which may make things easier

than they'd otherwise be.) $\:$ An $(r\hspace{-0.03 in}+\hspace{-0.06 in}1)\hspace{-0.02 in}$-time MAC will be used for messages from $P_2$,

since in addition to the puzzles (rather than the encoded-shares directly)

being tagged, $P_2\hspace{-0.03 in}$'s share of $b_j$ will be authenticated with $\: i = 0 \;$.

After the for loop reaches its end, $P_2$ will send that share and its MAC-tag to $P_1$.

Just like in my previous description, the rest of this description will ignore the MACs.

If $P_2$ aborts before sending the puzzle that encodes its share of $a_1$, then $P_1$ outputs $\neq$.

If $P_2$ aborts at any later time, then $P_1$ sets $c$ to be the solution to the most recent puzzle

and outputs $c_{\hspace{-0.03 in}\perp}$. $\:$ If $P_2$ sends its final message then $P_1$ and $P_2$ both output $b_j$.

If $P_2$ does not get $P_1\hspace{-0.04 in}$'s simulated-share of $b_{j-\hspace{-0.02 in}1}$ then $P_2$ outputs $\neq_{\hspace{-0.03 in}\perp}$.

If $P_2$ gets that but does not get $P_1\hspace{-0.04 in}$'s share of $b_j$ then $P_2$ outputs $\perp$. $\:$ If $P_2$ gets $P_1\hspace{-0.04 in}$'s share of $b_j$

but $P_1$ aborts before sending its final message, then $P_2$ sets $c$ to be $b_j$ and outputs $c_{\hspace{-0.03 in}\perp}$.

.

That sort of idea can in fact be used can be used for securely computing arbitrary functions,

by modifying how I was describing their use for equality so that [for $i$ from $1$ to $i^*\hspace{-0.06 in}-\hspace{-0.06 in}1$,

$a_i$ will be $\perp$ rather than $\neq]$ and [the rest of the $a$s will be set to the function's output] and

replacing ["then $P_1$ outputs $\neq$","outputs $c_{\hspace{-0.03 in}\perp}\hspace{-0.02 in}$","then $P_2$ outputs $\neq_{\hspace{-0.03 in}\perp}\hspace{-0.02 in}$"] with ["then $P_1$ outputs $\perp\hspace{-0.03 in}$",

"if $c$ is $\perp$ then that party outputs $\perp$ else that party outputs $c_{\hspace{-0.03 in}\perp}\hspace{-0.03 in}$","then $P_2$ outputs $\perp \hspace{-0.03 in}$"] respectively.

(That is quite different from the traditional way of using time-lock puzzles for something

resembling fairness, which is to decrease $T$ geometrically between pairs of messages.)

However, protocols using time-lock puzzles as I described

for computing equality has the advantage of offering something non-trivial

in the way of fairness to $P_2$ even if $P_1$ can quickly break the puzzles.

(There was a non-proof after this sentence, but it was just for my conversation

with Yehuda Lindell, rather than being related to the rest of this answer.)


Help me describe/identify this challenge-response protocol/algorithm? My area of expertise is reverse engineering, specifically embedded systems. I do attack cryptographic systems, but this largely involves key recovery or exploiting the implementation.

I was asked to reverse engineer a simple Windows executable used as part of a challenge-response protocol used for intruder alarm systems. This was trivially easy. I would like some assistance in describing the protocol/algorithm, so that I can look into the security of the system more.

The protocol

The protocol is designed to stop users resetting their alarm without contacting their alarm receiving centre.

When the alarm is triggered, a message is displayed:

CONTACT ARC
QUOTE 83647

This is called the "quote code" and is always numeric and 5 digits long. I don't know how it is chosen, but it appears random.
The alarm user calls the alarm receiving centre and informs them of the quote code.
The alarm receiving centre inputs the quote code into a piece of software (the "decoder") which returns the numeric 5 digit "reset code".
The user is informed of the "reset code" and inputs it into the alarm. It is accepted and the alarm is disarmed.

The alarm and alarm receiving center share a secret which is a number from 0-255, this is called the "version".

So at a superficial level, both the alarm and alarm receiving centre are doing:

ResetCode = F(QuoteCode, Version)

Where the QuoteCode and ResetCode are integers in the range 00000-99999 and the Version is a number between 0-255.

Algorithm implementation

This is my basic implementation of the algorithm used to generate the reset code given the quote code. The vector at the top is altered, but the rest is the same.

# Taken from the data in the exe
vector = [3,3,5,5,8,1,3,9,8,0,5,9,3,9,4,1,1,0,9,4,3,0,2,2,8,4,3,2,8,4,9,4,1,3,3,3,3,8,5,3,0,2,4,3,2,1,8,9,0,5,4,3,9,5,8,3,9,9,1,0,0,9,9,3,3,8,2,
         1,4,9,1,4,9,2,9,0,9,5,3,9,5,3,3,5,9,1,0,2,9,3,2,1,2,9,8,0,4,9,4,2,3,9,4,0,1,8,5,3,3,9,9,1,0,5,9,3,8,9,4,8,4,2,3,1,0,3,9,4,8,2,0,4,3,3,
         1,0,5,2,8,3,3,5,2,8,3,2,9,5,2,1,2,4,4,3,0,4,2,3,4,1,8,2,9,1,0,5,1,8,2,4,3,5,1,0,3,8,5,3,2,1,1,3,9,3,2,3,5,8,3,9,0,3,2,3,5,3,8,4,0,3,9,
         1,9,3,0,2,9,3,8,1,4,2,8,4,0,1,9,1,0,1,2,1,3,5,3,3,9,0,2,1,4,1,2,3,4,3,4,9,5,3,5,9,3,1,3,9,4,0,3,2,3,3,4,4,2,1]

def generate_reset(quote, version):
    i = 0
    tens = 0
    reset = []

    while i <= 4 :
        j = 0
        result = 0

        while j <= 4:
            offset = (version + tens + quote[j]) % 256
            result = result + vector[offset]
            tens = tens + 10
            j = j + 1

        reset.append(result%10)
        i = i + 1

    return reset

print(generate_reset(quote = [0,0,0,0,2], version=131))

I have run several simulations (simply by looping through all combinations of inputs), and noted the following:

The coverage of reset codes for any given version number across all quote codes is ~63%. This means that you have a higher than 1/100000 chance of guessing the correct reset code randomly.
Given a quote code and reset code, most of the time there is only a single valid version number. At most, two pairs of quote and reset codes are needed to derive the version number. The "version" isn't very secret as a result.

Questions

I hope these aren't too vague, or broad.

What would you call the type of algorithm? To me it looks like a hash with a key - does this make it a MAC?
Does this specific implementation have a name? It looks very "roll your own" but the vendor uses the phrase "military grade".
Are there any glaring issues with this algorithm? (I'm not expecting someone to do a full analysis, just some pointers would be great). My gut feeling is that the secret "version number" is not long enough to provide adequate secrecy.

The intend appears to be that vector is secret and the main key; and version (that, we are told, is secret) is an extension of that key (or variant selector).

1) I could say that ResetCode is a MAC of quote with key vector and version.

2) Never met this particular one. Anyone with common sense should laugh at it as snake oil if it pretends to be military-grade cryptography.

3a) When seen as a MAC, an obvious algorithmic flaw is that adding 1 (mod 256) to version and subtracting 11111 from any quote which has each of its digits non-zero leaves the ResetCode unchanged; this can be classified as a related-key weakness. That observation can make a usable paper tabulation of the function over twice less bulky (only entries with quote including a 0 need to be tabulated). Adding 10 (mod 256) to version also has special properties.

3a') Update: there's much worse! For constant version and vector, changing a particular digit in quote into another digit causes a difference (mod 10) in any particular digit of ResetCode that is independent of the 4 other digits of quote. With this observation, from the ResetCode for a small set of quote values, we can compute the ResetCode for any quote value, without knowing vector or version. The set of 46 quote values having at most one non-zero digit is convenient for hand calculation, but even random quote from a significantly smaller set often allows trivial linear algebra to pull that trick. In fact that MAC is so linear and with poor mixing that it could be broken from examples alone, without knowledge of the algorithm or reverse engineering the code or extracting vector!

3b) In the usage context, after vector has become public (e.g. if it is common to all alarms of the type), most often a single intercept of (ResetCode, quote) is enough to find version, leading to total break. Even a theoretically perfect cryptographic MAC is expected to have this property, given the ridiculously small size of what remains of the key (version), and the larger size of ResetCode. Any theoretical weaknesses of the algorithm seen as a MAC is moot compared to this system weakness of a small version when an adversary can obtain all key material beside version, or has access to a black box computing ResetCode for any chosen input (quote, version).


Why use symmetric encryption in a protocol like UPORT? Reading the whitepaper
UPORT: A PLATFORM FOR SELF-SOVEREIGN IDENTITY ~ DRAFT VERSION (2016-10-20)
I noticed it states :

Let A be an attestation. Suppose we wish to share this attestation with only identities X, Y and Z. We first generate a random symmetric key k, and encrypt A symmetrically. We denote this ciphertext sym(k, A).
Now we assume that X, Y and Z each have a public encryption key. Let asym(U,V,d) denote the asymmetric encryption between identities U and V of some data d. Specifically asym(U,V,d) = sym(DH(U,V),d)
Where DH(U,V) is a symmetric key generated from the public key of U and the private key of V using a Diffie-Hellman key exchange.
Create a random and ephemeral public/private key pair R, and create the data blob made up of ( sym(k,A), asym(X,R,k), asym(Y,R,k), asym(Z,R,k) )

Why is A encrypted symmetrically?
Reading the Security.SE questions “Why is symmetric encryption still used? [duplicate]” and “Asymmetric vs Symmetric Encryption” a potential reason for using symmetric encryption is speed but I don't see the context reasoning for using it in this specific case?

It's multi-layered encryption. If you "layer" your encryption you gain quite some nice flexibility features which is what they have done here.

You have some secret ($A$) which you only wish to share with parties $X,Y,Z$ for which you also know the public key. So what you do is that you first pick a random public-private-keypair $R$ yourself and derive a new shared secret with each of them. Now you have three shared secrets which would mean you'd have to encrypt three different copies of your message $A$. Instead you only encrypt a key $k$ three times using the shared secrets (using DLIES) and then in turn use $k$ to grant access (by means of symmetric encryption) to $A$. This approach saves you quite a bit of bandwidth and computational power there as you only need to encrypt a large message once instead of three times.

In a graphic, this process would look like this (don't forget that $k$ is small and $A$ is potentially large):


Existence of 99% successful unbounded adversary against randomized secret key encryption scheme with short keys It can be shown that if $E$ is a deterministic encryption with key of length $n$ and messages of length
$l\geq n + 10$ then there exist two messages $m_0$, $m_1$ and a strategy for Eve so that
given an encryption $c = E_{k}(m_b)$ for random $k$ and $b \in \{0, 1\}$, Eve can output
$m_b$ with probability at least $0.99$. (Eve is computationally unbounded)

Proof is shown here (in the last page): http://www.boazbarak.org/cs127/chap01-introduction.pdf

Now, I would like to prove the exact same thing for random encryption algorithms that use, say n, random bits.
The problem is that the set of all possible encryptions of a certain message can be much larger. Let's say $E$'s random bits are $r\gets\{0,1\}^n$ drawn uniformly, then the set $\{E(m;r)\}_{k,r}$ can have size $2^{2n}$ which might be (much) larger than $2^l$ where $l$ is the length of messages.

Comparing to the deterministic proof, it is not hard to show that if we still choose $m_0$ arbitrarily and use the same kind of decision rule for $A$ the adversary, there exists a randomized $E$ and some $m_0$ such that for every $m_1$ the probability for $A$ to be correct is bad. So in order to deal with the randomized case, we must not choose $m_0$ arbitrarily or come up with a new decision rule for $A$.

Our only assumption is that $D_k(E_{k}(m;r))=m$ for all $r,m,k$. (The decryption algorithm cannot "miss")

I was wondering if anyone could offer a useful observation or any hints.

Eventually, I was able to solve this question.
For anyone wondering, my problem was (mainly) the generalization of the deterministic adversary decision rule to the randomized case.

Originally, the deterministic decision rule was $$A(ct)=\begin{cases}m_0 & ct\in\{E_{sk}(m_0)\mid sk\in\{0,1\}^n\}\\m_1 & otherwise\end{cases}$$
And I generalized it to
$$A(ct)=\begin{cases}m_0 & ct\in\{E_{sk}(m_0;r)\mid sk\in\{0,1\}^n,r\in\{0,1\}^n\}\\m_1 & otherwise\end{cases}$$
But the good generalization would be
$$A(ct)=\begin{cases}m_0 & m_0\in\{D_{sk}(ct)\mid sk\in\{0,1\}^n\}\\m_1 & otherwise\end{cases}$$

Also, this time around you fix $m_1$ and check out random $m_0$'s.
Well, the names do not really matter, but the point is that the decision rule depends on the random message, not the fixed one.


Proof of storage scheme I'm familiar with client puzzles, where the client performs some work and there is a way to prove to the server that the client has done so.

Is there a way to do this, but where the client's resource is memory (storage) rather than computation (CPU)?  In other words, the client ties up some storage for some duration, and there is a way to prove to the server that it has done so.  I would like it to be much cheaper for the server to verify than it is for the client to do this work.

The motivation is that this might serve some similar benefits as client puzzles, deterring Sybil attacks with mass denial-of-service, in cases where the clients have a relationship with the server over a period of time -- in a way that hopefully can't be sped up by GPUs, FPGAs, and similar tricks.

I know that we could have the client generate a certain amount of random data and then use schemes for proof-of-retrievability/proof-of-data-possession to let the client prove that it is storing this data for the duration.  However, I'm wondering if we can do better in this setting, given that the exact data is not important, we just need a way to show that the client has tied up its memory (the equivalent of conspicuously burning a $1 bill, to prove that you are wealthy).

The paper "Proofs of Space: When Space is of the Essence" proposes a scheme that allows a client to prove that it has read/write access to at least $B$ bytes of memory.  Basically, the server gives the client a function $f$ that requires at least $B$ bytes to compute, and the client proves it can compute $f$.  The method is complicated and I haven't absorbed all of the machinery.

One of the lead developers of Bitcoin has proposed a different scheme, which allows the client to prove that it is "tieing up" a certain amount of space over time.  The server can periodically send the client a challenge; if the client can always respond correctly, this proves that the client must have set aside that much space.

The idea behind the latter scheme is not too complex.  Basically, we form a GGM hash tree: for a complete binary tree of depth $d$, with a random 160-bit seed at the root, and then recursively label all of the nodes of the tree as follows: if a node has label $x$, then its left child has label $H(x||0)$ and its right child has label $H(x||1)$, where $H$ is a cryptographic hash function.  There are $2^d$ leaves.  Each leaf can be thought of as a pair $(i,x)$, where $i \in \{0,1\}^d$ is the index of the leaf (a binary string indicating the path taken from the root to that leaf) and $x$ is the label on that leaf.  Now sort these pairs on their $x$-values.

At any point, the server can challenge the client by picking a random index $i$, computing the label $x$ on that leaf (this takes just $d$ evaluations of $H$, and can be done by the server, since $H$ is publicly known), sending $x$ to the client, and asking the client to send back the corresponding index.  If the client has been tying up enough space to store all $2^d$ records, it can quickly find the corresponding $(i,x)$ pair and send back the correct value of $i$; if it hasn't, it will find it difficult to respond correctly.


Identity-Based Encryption consist of four algorithms. Extract phase is one of them and it is done by PKG or receiver? The Identity-Based Encryption consist of four randomized algorithms: Setup, Extract, Encrypt, Decryption. The Setup phase is done by Private-key generator, Encrypt by sender and Decryption by receiver. the Extract phase is done by PKG or receiver?

The Extract phase is performed by the Private Key Generator (PKG). Note that in IBE it is not necessary a Public Key Generator, since public keys are just arbitrary bit strings or "identities". So, to sum up:

Setup, executed by the PKG. This algorithm creates, among other things, a master key for the PKG.
Extract, executed by the PKG. This algorithm enables the creation of the corresponding private key for an arbitrary identity. The PKG needs the master key for doing this.
Encrypt, executed by the sender, who only needs to specify the receivers' identity.
Decrypt, executed by the receiver, who is in possession of a private key that must be generated by the Extract algorithm.

This is much better explained in the Wikipedia.


DH Key Exchange Protocol (one-out-of two) Now given this problem, for part 1) I have solved it as follows, (I hope I am correct).
The basic idea is this:

I Have two prime numbers g and p and I tell you what they are.
You choose a secret number (a), you compute ga mod p and send that result back to me. (call it A).
I do the same, and call my number b and B respectively. So I compute gb mod p and send you the result B.
You take the number that I sent and perform the same operation,Ba mod p.
And likewise for me: Ab mod p.

Therefore step 5 is the same is as Step 4 due to modular exponentiation giving us the shared secret key (could also be between Alice and Bob).

(ga mod p)b mod p = gab mod p
(gb mod p)a mod p = gba mod p

Now for Part 2 and Part 3 I am not sure how to solve this - so any help would be kindly appreciated  - please as I have an exam question that will be similar. Thanks guys!

Sonia.

For question 1, Alice computes $k_0 = B^a, k_1 = (B/A)^a$, and Bob computes a key $k = A^b$. If $c=0$, then $B = g^b$, hence $k_0 = B^a = g^{ab} = A^b = k$; else, if $c=1$, then $B = Ag^b$, hence $k_1 = (B/A)^a = g^{ab} = A^b = k$. In any case, both players have a shared key (either $(k_0,k)$ or $(k_1,k)$).

For question 2, let me give you some hints. Bob generates $B$ according to one of two distributions: (I write $b \gets_{\mathsf{R}} \mathbb{Z}_p$ to indicate that $b$ is taken uniformly at random over $\mathbb{Z}_p$), $D_0 = \{b \gets_{\mathsf{R}}\mathbb{Z}_p: B \gets g^b\}$ and $D_1 = \{b \gets_{\mathsf{R}}\mathbb{Z}_p: B \gets Ag^b\}$. What can you tell about those two distributions? Why cannot one distinguish them, even with unlimited computational power? Additional hint: $A = g^a$; what can be said about the distribution of exponents $a+b \bmod p$ when $b$ is taken at random from $\mathbb{Z}_p$, but $a$ is fixed?

For question 3, let us suppose that there is a player, Bob, that is able to compute both $k_0$ and $k_1$ with some fixed probability $\epsilon$ after performing a one-out-of-two key exchange with Alice. Suppose now that you are given a challenge for the computational Diffie-Hellman problem: you receive the description of a group $\mathbb{G}$, as well as a tuple $(g, X= g^x, Y = g^y)$. You break the CDH assumption if you manage to return $Z = g^{xy}$ with some non-negligible probability. Therefore, your goal is now to construct a $Z$ which will have a good probability (related to $\epsilon$) to be equal to $g^{xy}$, by interacting with Bob: you'll play a one-of-of-two key exchange with him, using carefully chosen elements from the CDH challenge instead of picking group elements according to the specification of the key exchange. Then, you'll reconstruct $g^{xy}$ with good probability using the keys $k_0,k_1$ that Bob returns (recall that they have a probability $\epsilon$ to be the correct keys).

I've given many details, so you should be able to figure out how to properly answer the question by now. If you are still blocked, if there is something you do not understand, please do not hesitate to mention it and I'll provide further insights.

EDIT: further insights for question 3.

Suppose now you received $(g, X= g^x, Y = g^y)$. We will play Alice's role in a one-out-of-two key exchange. As you remarked in your comment, we cannot gain anything from the values $B=g^b$ chosen by Bob - as it is chosen by the adversary, he can always compute it. However, we can gain something from the fact that Bob will compute both $k_0 = B^a$ and $k_1 = (B/A)^a$: we can deduce $A^a$ from that by computing $k_0/k_1$. Note that $A^a = g^{a^2}$.

Let me sum up: we have an adversary Bob, to which we can send some $A = g^a$ and who eventually returns two keys. At the end of the interaction with Bob, by computing $k_0/k_1$, we recover $g^{a^2}$ (with probability at least $\epsilon$, as this is the probability that both keys are correct).

So, we can now see Bob as an oracle which returns $g^{a^2}$ when we send it $g^{a}$. Given such an oracle, solving the CDH problem is a standard exercise. Can you see how it is done? The trick is simply: use the identity $ab = 1/2((a+b)^2 - a^2 - b^2)$. Now, from the "exponent squaring oracle" and $g^x,g^y$, you should be able to find out $g^{xy}$.

If you still do not see how to solve the exercise, I'll give you the entire solution, but it's way more interesting and useful for you if you figure it out for yourself.


PAKE password change Is there any way to change a password using a PAKE-like algorithm, without the server getting the plaintext of either the old or new password?

If you use an augmented PAKE (such as AuCPace or Opaque), the server never gets a copy of the password in the first place.  Hence, to update the password, you would reregister with the new password, but the reregistration process wouldn't involve sending the password.

If you use a balanced PAKE (such as Spake-2), well, the server does need the password.

Augmented PAKEs are designed to be used in a client-server scenario (where the client always initiates the negotiation, and we don't want the server to have the password in the clear); balanced PAkES are designed for peer-to-peer scenarios (where either side may want to initiate it, and so both sides need the password)


Differences between the terms "pre-master secret", "master secret", "private key", and "shared secret"? Both crypto.SE and security.SE have excellent Q&As about how TLS generates session keys (I have linked some at the bottom).

In reading these threads I'm having troubles with terminology since the following terms seem to be used with overlapping contexts, though they are clearly different concepts. Reading definitions is only partially helpful since they don't show the differences between their usages.

pre-master secret
master secret
private key
shared secret / session key

As I understand it, the pre-master secret is related to private keys, but is algorithm independent, and the master secret is (often?) used as the session key. But I'm sure there's more nuance to the definitions.

Related Questions:

How does SSL/TLS work? [security.SE]
What's the point of the pre-master key? [security.SE]
What is the purpose of pre master secret in SSL/TLS? [crypto.SE]
What's the difference between the long term key and the session keys? [crypto.SE]

Simplified SSLv3/TLS from this book Note, $R_{(Alice|Bob)}$ is a random nonce chosen by Alice or Bob respectively, and $\{S\}_{Bob}$ is encryption with Bob's public key.

pre-master secret

As stated in one of the answer you link to, "The point of a premaster secret is to provide greater consistency between TLS cipher suites."

In the figure above, the premaster secret is $S$ (in message 3). In this case, it is randomly generated. It could come from a diffie-hellman exchange, or some other method, depending on the agreed upon cipher suite.

It isn't really "related to the private keys" but how it is generated/agreed upon depends on the cipher suite chosen in the second message of the figure.

master secret

In the figure above, the master secret is $K$. Shown on the sides, it is a function of the pre-master secret and the two random values sent in the first two messages.

private key

I'm not really sure where this comes from. It could refer to the Bob's private key for the certificate sent in message 2. It could also refer to private keys used in a diffie-hellman key exchange. If doing client authentication, it could refer to the client's private key associated with their certificate.

shared secret / session key

This is what is referred to in the last step of the figure. The session key is referred to as "keys derived from K". Many keys are actually derived from K. This could be the encryption key, integrity protection keys (for say HMAC), IVs for the ciphers, etc. And, it is usually a different set for each direction.


Setting up of polynomials for CP-ABE or KP-ABE Access Trees My question I guess is how the selection is done. A brief explanation with a simple access tree will be very helpful.

I suggest, you look into the code how that works. Basically, you start with a secret that you want to share according to some tree. You share the secret with a Threshold Secret Sharing Scheme like Shamir's Secret Sharing and put the resulting shares into the children of that node (in the beginning this is the root node). Then you can re-share each of the shares if this is necessary. Here is an example:

In the end, every non-leaf node in the tree has its own polynomial that has to be evaluated and every leaf node has a share. In the reconstruction phase, you apply Lagrange interpolation at each node from the bottom up.

Of course, it is possible to make some optimizations. For example, if the root node is an OR gate and the left subtree is large, but the right subtree is only a single leaf, then you should first check whether the right subtree is satisfied and reconstruct the root secret only from one leaf.


Permuting Small Sized Set in Practice Imagine we have a set $S$ of $m$ elements and we wants to permutes the set elements. Thus the original position of each element should be unknown after permuting. If we define a permutation function as $\pi: \{0,1\}^n \rightarrow \{0,1\}^n$, then the set elements are permuted securely if $n\le|S|$ where $n$ is the security parameter. So to permute $S$ we do $\pi (i)=r_i$, where $i$ is the original index of an element in the set, and $r_i$ is its new index.

However, if the set size is small ($|S|< n$) it seems the only way to securely permute it is to pad it first and then permute it, that increases storage cost.

Question: Is there any better and more cost effective way of permuting a set than the above scheme?

If you can generate uniform random numbers, you can use a variant of Fisher-Yates.

//given an array s with the elements to be permuted
for i from n-1 to 1:
    t = rand(0, i) # inclusive
    swap(s[i], s[t])


How to put the hash of a PDF file in the PDF file? I know it sounds strange.. but, are there any ways in practice to put the hash of a PDF file in the PDF file? And after geting the hash in the PDF file - if someone would do a hash check of the PDF file, the hash would be the same as the one that is already in the PDF file? :) maybe with MD5, since it's known to have weaknesses? Example:

[user@notebook ~] wget -q http://renyi.hu/~csirmaz/nws06/xajanlo.ps -O Md5-xajanlo.ps; wget -q http://renyi.hu/~csirmaz/nws06/xutasit.ps -O Md5-xutasit.ps; md5sum Md5-xajanlo.ps; md5sum Md5-xutasit.ps; sha512sum Md5-xajanlo.ps; sha512sum Md5-xutasit.ps; rm Md5-xajanlo.ps Md5-xutasit.ps
583bdceb34826c38ac7f1fdac3aca807  Md5-xajanlo.ps
583bdceb34826c38ac7f1fdac3aca807  Md5-xutasit.ps
c82d26f77ccd4597622fc985d4220aedad6f866555c6db82db2d6d17e22016268a3e88d0b0cd89a8e536ae7d666c446edeb77edef2fca783739e4bff9d7032be  Md5-xajanlo.ps
205c18b396bee84995d8c325787600ca88ca3d9758c4dfe89cdaa242ab9513710057c5fce55afb2c6ef3117703be7c31266a1fa6fbac1f369b82f0719587c60c  Md5-xutasit.ps
[user@notebook ~]

You cannot push the hash of a file 'in' the file, as newly modified file will have a different new hash....

As said, it seems that you are asking a way to solve this equation H(∗∗a∗∗∗)=a


Is there a complete list of Signature Algorithm names? I need to analyze the output of rbsec's sslscan which reports a server's SSL/TLS configuration as reported by OpenSSL.

I'm interested in the Certificate's Signature Algorithm in particular, and I was hoping to find a complete list of possible values for this entry. During some quick tests, I saw that sslscan reports the long name for the algorithm. For example, RSA encryption with a SHA-512 hash is reported as "sha512WithRSAEncryption".

<certificate>
  <signature-algorithm>sha256WithRSAEncryption</signature-algorithm>
  ...
</certificate>

I've been trying for hours to pin down where these strings come from, and it seems that they aren't from the RFC specification for SSL (RFC 6101), but I could be wrong about that. I did find the names in OpenSSL's obj_dat.h file, however that header file contains a significant number of defined strings which are clearly not also signature algorithms.

  ...
  {"id-ppl-independent", "Independent", NID_Independent, 8, &so[4500]},
  {"RSA-SHA256", "sha256WithRSAEncryption", NID_sha256WithRSAEncryption, 9, &so[4508]},
  {"RSA-SHA384", "sha384WithRSAEncryption", NID_sha384WithRSAEncryption, 9, &so[4517]},
  {"RSA-SHA512", "sha512WithRSAEncryption", NID_sha512WithRSAEncryption, 9, &so[4526]},
  {"RSA-SHA224", "sha224WithRSAEncryption", NID_sha224WithRSAEncryption, 9, &so[4535]},
  {"SHA256", "sha256", NID_sha256, 9, &so[4544]},
  ...

Is there a list of the (OpenSSL specific?) long names for the Signature Algorithms that OpenSSL reports? Preferably one that is easily digestible for a program or human?

You can find a list in the bouncyCastle source code for Asn1SignatureFactory, here:

https://github.com/kerryjiang/BouncyCastle.Crypto/blob/master/Crypto/x509/X509Utilities.cs

In addition to that, you can list all registered SSL-digest-methods with the following C-Code:

#include <openssl/evp.h>
#include <openssl/objects.h>
#include <stdio.h>

void my_callback(const OBJ_NAME *obj, void *arg)
{
  printf("Digest: %s\n", obj->name);
}

int main(int argc, char *argv)
{
  void *my_arg;
  OpenSSL_add_all_digests(); //make sure they're loaded

  my_arg = NULL;
  OBJ_NAME_do_all(OBJ_NAME_TYPE_MD_METH, my_callback, my_arg);
}

The callback receives objects of type OBJ_NAME:

typedef struct obj_name_st {
    int type;
    int alias;
    const char *name;
    const char *data;
} OBJ_NAME;

You can look up the associated EVP_MD* via EVP_get_digestbyname().
This method finds a lot of things, many of which you probably don't want:

$ ./a.out
Digest: ripemd160WithRSA
Digest: ssl2-md5
Digest: sha384
Digest: sha224
Digest: SHA224
Digest: md4
Digest: sha512
Digest: RSA-SHA256
Digest: DSA-SHA
Digest: sha1WithRSAEncryption
Digest: MD5
Digest: MD4
Digest: ssl3-sha1
Digest: ripemd160
Digest: sha
Digest: SHA384
Digest: SHA1
Digest: ssl3-md5
Digest: sha256
Digest: sha384WithRSAEncryption
Digest: SHA512
Digest: DSA-SHA1-old
Digest: dsaWithSHA1
Digest: ecdsa-with-SHA1
Digest: whirlpool
Digest: RSA-RIPEMD160
Digest: rmd160
Digest: RIPEMD160
Digest: RSA-SHA1-2
Digest: RSA-SHA1
Digest: dsaWithSHA
Digest: md5WithRSAEncryption
Digest: DSS1
Digest: RSA-MD5
Digest: dsaEncryption
Digest: ripemd
Digest: md4WithRSAEncryption
Digest: DSA
Digest: sha512WithRSAEncryption
Digest: SHA
Digest: dss1
Digest: RSA-SHA224
Digest: RSA-SHA512
Digest: SHA256
Digest: md5
Digest: RSA-SHA384
Digest: sha1
Digest: sha224WithRSAEncryption
Digest: RSA-SHA
Digest: shaWithRSAEncryption
Digest: sha256WithRSAEncryption
Digest: DSA-SHA1
Digest: RSA-MD4


Hash ratchets with truncating hash function I'm working on a forward secret messaging system that relies on hash ratchet. I'm using BLAKE2b as the one-way function, which by default produces 512-bit digests. These digests are truncated by my software to 256 bits using the digest_size parameter of the Python implementation before they're used as key in XChaCha20-Poly1305. Using a simplified example, is

key = os.urandom(32)
while True:
    ct = encrypt(key, input('Message: '))
    key = blake2b(key, digest_size=32)

a secure construction, or does the key lose entropy with every ratchet step? If yes, should I use BLAKE2s instead?

Collisions in the hash will make fewer and fewer keys possible based on the number of iterations, resulting in a sort of "entropy loss". (Aside, I don't think "entropy loss" is the correct term as the system is deterministic and the entropy is provided by the original key.)

Importantly, though, the effect will be very small with a 256 bit hash, as covered by this question.

In short, "yes, but not enough to matter from a security perspective".

I would add a 64-bit counter variable to that hash step as is done in some KDF and password-hashing constructions to ensure there is no chance of falling into a short cycle of keys - no matter how unlikely such a cycle would be.


Does hash_df use binary or an ASCII hexadecimal representation for numbers to be passed to the hash function? I'm implementing the HASH_DRBG algorithm.
As per NIST-SP800 90 document for HASH DRBG Generation, section 10.4.1 "Derivation Function Using a Hash Function (Hash_df)", the Hash_df algorithm contains this step 4.1:

  temp = temp || Hash (counter || no_of_bits_to_return || input_string).

I believe || here represents "append" operation. According to the algorithm, do I have to make the append operation and hashing on an ASCII hex string or a binary string?

Example, I can do
Hash  ("000102030405060708090A0B0C0D0E0F101112131415161718191A1B1") where the input is ASCII string characters. Or I can do Hash(&bytearray) where bytearray stores the non-ASCII numbers in binary?

Which one is expected as per the algorithm? I am planning to use SHA-1 or SHA-256 as Hash here.

In step 4.1 of the algorithm:

Counter is expected to be a 1 byte binary value
no_of_bits_to_return is a 4 byte bigendian binary value
input_string is a variable length binary value
$||$ is concatination (just like you guessed)

So, Hash(&bytearray) would be appropriate.

The trickiest part is the 'no_of_bits_to_return' -- that's bigendian (and so a value of 24 would be represented by the four bytes 0x00 0x00 0x00 0x18), which is the opposite of how the most common processors internally represent a 4 byte value.

Now, if you were to convert to (say) ASCII hex first, well, it probably won't affect the security of the algorithm; however, it won't be the HASH_DRBG algorithm, but something else.


One Step Decryption For Multiple Chained Encryptions If we have a encrypting function f(x, y) (x for input, y for key) and let's say we composite this function n times inside itself with the same y (like f(f(f(x, y), y), y)) and set the output to be z. Does there exist another function g(v) so that g(z)=x? Can this be proven for any kind of encryption function f(x, y) stacked inside itself any times? Thanks.

By definition, there exists such a function.  Your function $g(z)$ could be simply a table of all the possible values of $f(f(f(x, y), y), y)$ mapped back to one of the possible values of $x$.

I think that what you're asking is whether there is an efficient algorithm for unwinding this chaining.  Generally, with cryptographic algorithms, the answer is no, and this is intentional (see RichieFrame's comment about nonlinearity).

There are exceptions, though.  For example, with "raw" RSA, $f(x, y) = x^y \mod n$, for whatever $n$ is used alongside $y$ as the public key.  Then:

$f(f(f(x, y), y), y) = ((x^y)^y)^y \mod n = x^{y^3} \mod n$

Let $d$ be the private key (exponent) corresponding to $y$.  Then, you have:

$g(z) = z^{d^3} \mod n = x \mod n$.

In general, this property is something to avoid, because it often allows attackers to modify the contents of an encrypted message (to something useful) without being able to decrypt the message.  In the case of "raw" RSA, it leads to attacks; real RSA implementations use padding to make RSA not have this property.

Closely related: malleability


Keys in HMAC and NMAC I'm quite new to this topic and have several questions concerning HMAC and NMAC:

Why does NMAC need two keys? How can it be attacked if we just used some sort of initialization vector instead of the first/second key?
What is the purpose of ipad and opad in HMAC?
What if the key is longer than the block size?
Can the key be longer than the number of input bits of a hash function?

NMAC is really just an "education tool" on the way to HMAC and I don't think anyone intended it to be used. The two keys are needed since the first and second hashes have different purposes. The first hash on the message is just needed to get collision resistance, whereas the second hash is supposed to provide a pseudorandom function type property. As such, it actually suffices to have just one key (on the second hash). However, the first key is included as a conservative measure so that even if the hash is broken and collisions can be found, it does not mean that NMAC/HMAC are broken since the attacker has to find a collision where a key is used that it doesn't know. The best way to look at NMAC/HMAC is a specific implementation of "hash and MAC" (analogous to "hash and sign").

The purpose of ipad and opad in HMAC is to get computationally independent keys for the first and second hashes. If we assume that the compression function acts like a pseudorandom generator when used in this special way with ipad and opad, then this follows. (It of course follows immediately in the random oracle model, but this is overkill and not needed.)

Nothing inherently bad happens if the key is longer than the block size, but nothing is gained either.

I'm not sure what you mean by the key being longer than the number of inputs bits of the hash function. I guess that you mean the compression function (since the hash function is practically unlimited). If yes, then the key can be longer, but nothing is gained by it, so you shouldn't do it.


How can I instantiate a generalized hash function? I've come across a bunch of "strange" hash function notations, such as the following ones and now I don't know how to choose / instantiate them.

Can you please explain me what this notation means and how I can actually instantiate such a hash function?

The notation in question:
$$H_1:\mathcal M \rightarrow \mathbb F_p$$
$$H_2:\mathcal M \rightarrow \mathbb Z_n^*$$
$$H_3:\mathcal M \rightarrow \{0,1\}^l$$
$$H_4:\mathcal M_1\times ...\times \mathcal M_k\rightarrow \mathcal S$$

where $\mathcal M\in\{\mathbb F_p,\mathbb Z_n^*,\{0,1\}^*,\mathbb G,...\}$ where $\mathbb G$ is a generic (but there instantiated) group and $\mathcal S\in\{\mathbb F_p,\mathbb Z_n^*,\{0,1\}^l\}$

Can you please explain me what this notation means?

Of course, $f:A\times B\times C\rightarrow D$ is fancy mathematican's language for saying: "a function f, that takes an element from A, B and C (in this order) and maps this to an element of D" (arbitrarily extend this explanation to as many arguments as you wish).

In this particular instance, the authors of these papers didn't actually care about which hash function should be used as long as it fulfills the usual properties of a hash and maps from the right set(s) to the right set, as the situation requires. For example if you want to derive a key from a shared Diffie-Hellman secret (which is an integer in $\mathbb F_p$ and nothing else) you formally need a hash function $H:\mathbb F_p\rightarrow \{0,1\}^l$, where $l$ is the desired length of the derived secret. The fact that you usually do this by hashing the binary representation of the integer doesn't matter for theoreticans.

  How I can actually instantiate such a hash function?

First, I'll discuss the case where you only have one argument from the set of binary strings, then this will be adapted to arbitrary sets for the arguments and finally will extend this result to multiple arguments.

Assume you want to instantiate $H_3:\{0,1\}^*\rightarrow \{0,1\}^l$. For this you take your favorite n-bit hash function $H$ (e.g. SHA-256, SHA-512, SHA3-512, SHA3-256, Skein-512-512, Blake2b-512, ...). Now you use a key derivaton function, such as HKDF to construct an arbitrary hash or KDF2, which just hashes the input and with a counter that increments as long as you need more bits (your zero-based counter will be $\lceil\frac{l}{n} \rceil-1$ at the end).

The next step is to turn this into a hash function that outputs an arbitrary number (from the finite field): $H_1:\{0,1\}^*\rightarrow \mathbb F_p$. To do this you take the generic hash function we just constructed and reduce the output $\bmod p$ and you're done, $l\geq \lceil \log_2(p)\rceil$ in this case. This will be good enough for most uses. If you strongly require a uniform distribution, pick $k\geq 2\cdot \lceil \log_2(p)\rceil$.
Note that if you want to hash into $\mathbb Z_n^*$ with $n$ being composite, then you can in theory get values that are not in this set (like $p$ or $q$ if $n=pq$), but the chance of this happening are negligible if $n$ is sufficiently large.

Expanding on that: If you have a domain (the set you map into), that cannot be trivially converted from a bit-string (like integers) or where membership criteria or non-trivial, you can build a deterministic hash function, that will increase a counter each time the result is not an element. For $\mathbb Z_n^*$ for example this would be $\gcd(r,n)=1$ for membership (given that $r$ is your hash output).

Expanding this approach to arbitrary input sets is straightforward. You basically just convert the set-element in question into a its bit-representation (which you'll have anyways in all practical applications) and then hash this as describe above.

The multi-argument case is a little more interesting. You use the prefix-free pairing function of your choice to combine the bit representation into a large binary string. If all but one of your inputs are fixed-length, simple concatenation will do here. Otherwise you may be able to construct collisions by appropriately choosing the inputs, for example (01,1) and (0,11) would result in the same string after concatenation, yielding an undesirable collision. Another possible construction for this would be to pre-hash each argument independently and concatenating the (fixed-length) outputs for final hashing.


Non Repudiation - Message Authentications methods According to a definition given by my professor:

  Message authentication methods verify that the message is from the
  right sender, however they don't guarantee non-repudiation.

To me this sounds like a contradiction, what does "right sender" mean?

When Alice and Bob are using a message authentication code (MAC) scheme, both of them have the shared MAC key, and both of them can generate valid MAC tags. Between Alice and Bob, they can be sure who is the sender. For example, if Bob receives a message with a valid MAC, and the message was not sent by himself, then the message must come from Alice. Hence "Message authentication methods verify that the message is from the right sender". Here essentially, MAC enables private verifiability among the two parties.

However, non-repudiation is about convincing a third party (or requires public verifiability). A third party, without the MAC key, when seeing a message with a MAC cannot verify the MAC is valid. Hence it has no way to decide who was the sender. Even if Alice and Bob give up the key, the third party can only say the sender is either Alice or Bob, since both of them can generate the tag. Thus Alice and Bob can always deny she/he was the message sender (and say the sender was the other party).


ECDH VS. DH benchmarking in JAVA So basically my problem is the odd result i get when measuring the time it takes to generate a ECDH key in java vs. the time it takes to generate a DH key.

I compare the time it takes to generate:

192bit ECDH-key to a 512bit DH-key
224bit ECDH-key to a 1024 DH-key

Now I expected the ECDH key pair generation to beat regular DH keys due to difference in key size, however that is not the case when I do it. Perhaps I'm measuring this wrong or is there another explanation.

    public void generateKeyPair() {

    try {

        keyfactory = KeyFactory.getInstance("ECDH");

        keyPairGenerator = KeyPairGenerator.getInstance("ECDH", "BC");

        //NIST EC-Curve P-224"
        org.bouncycastle.jce.spec.ECParameterSpec ecSpec = ECNamedCurveTable.getParameterSpec(EllipticCurveDiffieHellman.curveNames.get(new Integer(224)));

        keyPairGenerator.initialize(ecSpec, new SecureRandom());

    int num = 10;

        /* Warm up */
        for (int wRound = 0; wRound < 200; wRound++) {
            keyPairGenerator.generateKeyPair();
        }

        /*
         * Finding the right number of iterations such that we iterate for
         * at least 2s
         */
        for (;;) {

            long begin = System.currentTimeMillis();

            for (int i = 0; i < num; i++) {

                keypair = keyPairGenerator.generateKeyPair();
            }

            long end = System.currentTimeMillis();

            long time = end - begin;

            if (time >= 2000) {
                System.out.printf("Average keygen time: %.2f ms\n",
                        (double) time / num);
                break;
            }

            num *= 2;
        }

    } catch (Exception e) {
        e.printStackTrace();
    }
}

Generating an (EC)DH key pair entails "producing" the group parameters (the curve or the modulus+generator), then the private key $x$, (a random integer modulo the group order $q$), and then applying the private key to the generator (i.e. computing $xG$ on the curve, $g^x \mod p$ for plain DH). Producing new group parameters would be the most expensive operation, especially for elliptic curves; however, there is no security issue in reusing the same group parameters for several key pairs.

Most ECDH implementation focus on a handful of standard curves (a subset of the 15 FIPS curves) and never generate new ones. Generating new group parameters for DH is quite easier, but still expensive, which is why some implementations just reuse a few pre-generated parameters. Thus, the remaining operations for (EC)DH key pair generation are fast; we are in the milliseconds range.

Your code for measuring generation time fails to take into account the idiosyncrasies of Java. The first time an application accesses a class, it must load that class, which entails locating it in the Jar archives, reading it from disk, uncompressing it, decoding the class file format, and launching the initialization code for that class, which may do a lot of expensive things. Then, for each method, the first call to the method triggers the verification which is a flow analysis by which the JVM makes sure that the code complies to the Java typing rules. Finally, the first few invocations of the method will use interpretation; only methods which are invoked sufficiently many times will be translated to efficient native code (this is known as "JIT compilation").

All this translates to the following: to benchmark Java code, you must allow for some considerable "warm up". Also, you will want to run the code several times in a loop so as to get an average execution time because any single invocation can be substantially delayed in case, for instance, of a garbage collector run (the JVM aims at perceived smooth execution, but human beings do not perceive hiccups below about 20ms). So your benchmark code should look like this:

/* warm-up */
for (int i = 0; i < 200; i ++) {
    generateKeyPair();
}

/* find the right number of loop iterations such that we loop for at
   least two seconds */
int num = 10;
for (;;) {
    long begin = System.currentTimeMillis();
    for (int i = 0; i < num; i ++) {
        generateKeyPair();
    }
    long end = System.currentTimeMillis();
    long time = end - begin;
    if (time >= 2000) {
        System.out.printf("average keygen time: %.2f ms",
            (double)time / num);
        System.out.println();
        break;
    }
    num *= 2;
}


Identification by RSA Suppose we have identification scheme as such:

Bob takes random $r$, and encrypts it with Alices public RSA key $(n,e)$, sends $r^e$ to Alice.

Alice decrypts $r$ and sends it back to Bob, becomes identified.

Why it might be a bad idea to use same RSA key for following communication afterwards?

Well, consider if Bob is communicating with Alice; Bob sends Alice a random $r^e$, Alice recovers $r$ and sends it back.  Then, they proceed to use the same RSA modulus to negotiate a secret key; for example, Bob picks a secret value $m$, computes $m^e$, sends that to Alice, who recovers $m$, and then they both use $m$ to generate secret keys, and use those keys to exchange messages that they want to keep secret.

Here's what can happen; the NSA can then start communicating with Alice; they can send Alice the value $m^e$, Alice (thinking that this is someone else she is supposed to be talking to) recovers $m$, and sends it back.  The NSA now has enough information to recover the secret keys that Alice and Bob used to communicate.

And, if you're thinking "well, can't Alice remember the values that she used to communicate with Bob, and refuse to decrypt that", it turns out that's not sufficient.  What the NSA can do is pick a random value $k$, compute $k^e$, and send the value $k^e \cdot m^e = (km)^e$.  Alice will recover the value $km$, which will look like a random selection, and send that back; the NSA can then compute $km \cdot k^{-1} = m$, and is then able to decrypt the secret traffic.


Safety of a private key when knowing the full content of an encrypted message in case of fixed initialization vector When knowing the full content of the original message, will I be able to derive the private key from the encrypted message when the underlying encryption uses a fixed initialization vector?
Meaning if we encrypt by Text UNENCRYPTED x Private Key =[fixed IV]=> Text ENCRYPTED, can we somehow calculate the key backwards by Text ENCRYPTED % Text UNENCRYPTED =[fixed IV]=> Private Key, considering a fixed IV is used?
If the answer is no, please explain why this is not possible. If the answer is yes, will the calculated key really be the private key or just a local solution to this particular message, not suitable to decrypt other texts encrypted with the same unknown private key? (The latter would mean something like:  Text ENCRYPTED % Text UNENCRYPTED =[fixed IV]= Pseudo Private Key != Private Key)
(You might also note differently: fx(Text UNENCRYPTED, Private Key) = Text ENCRYPTED, so if fy(Text ENCRYPTED, Text UNENCRYPTED) = Private Key, how to get from the function fx to fy? If a fixed IV would not allow this, please mention some other encryption methods with which this backwards calculation would be possible)

What you're describing is called a known-plaintext attack, and any secure encryption algorithm should prevent this. If we take an encryption function with no IV $C = ENC(M, K)$ we should get a system where knowing both $M$ and $C$ reveals nothing about $K$.
We can expand this principal to $C = ENC(M \oplus IV, K)$ and simplify it back to the example without an IV; $M \oplus IV$ simply becomes our new $M$ (you could say $M' = M \oplus K$). This principal applies also for $C = ENC(M \oplus IV) \oplus IV$.
Any encryption algorithm which fails to achieve this property cannot be considered secure, and as such in your scheme $K$ will not be leaked if the encryption algorithm used is secure.
However, using a fixed IV is bad practice since it allows statistical analysis attacks (read about it here). While $K$ may not be leaked $M$ might leak from statistical patterns.


Group Signatures with VLR Revocation Check I was reading the paper by Boneh et al. Link. The scheme describes what is called a Verifier Local Revocation Technique. The Scheme assumes that a Revocation List [RL] allows each verifier to check the validity of the signature. The revocation check works as follows:

$e(T_2/A,\hat{u}) =^{?}e(T_1,\hat{v})$, Given $T_1 = A_iv^\alpha,T_2 = u^\alpha$
$e(A_iv^\alpha/A,\hat{u}) =^{?}e(u^\alpha,\hat{v})$

In the case that $A_i\in$[RL], $A = A_i$, then,

$e(v^\alpha,\hat{u}) =^{?}e(u^\alpha,\hat{v})$

The author then claims that these pairings are equal, The $(\hat{u},\hat{v})$ are generated as follows:

$(\hat{u},\hat{v}) \leftarrow H_0 = (gpk,M,r) \in G_2^2$ , Given that:
$u\leftarrow\psi(\hat{u})$, $v\leftarrow\psi(\hat{v})$,

  I have three questions:

Why the $(\hat{u},\hat{v}) \in G_2^2$ not $G_2$.
What is the Hash Function that generates two parameters and is there a relation between them?
How the check $e(v^\alpha,\hat{u}) =^{?}e(u^\alpha,\hat{v})$ is valid.

I do not have access to the paper you have linked, but I certanly can answer the first question and maybe answer the third question:

$(\hat{u}, \hat{v}) \in G_2^2$ is a short version of $(\hat{u}, \hat{v}) \in (G_2 \times G_2)$ which is a short version of "$\hat{u} \in G_2$ and $\hat{v} \in G_2$".
Since I don't have access to the paper I'm gonna make some assumptions to answer the third question:

$e$ is a bi-linear mapping of the form $G_1 \times G_2 \rightarrow G_3$. I make this assumption based on the fact the second parameter is element of a group called $G_2$ which hints at the existence of a group $G_1$.
$\psi$ is a linear homomorphism from $G_2$ to $G_1$. This would make sense as the first parameter of $e$ would be an element of $G_1$ under the first assumption. Also $\psi(g_2)$ must be $g_1$ for the math below to check out.

Be $x, y \in Z_q$ with $\hat{u} = g_2^x$ and $\hat{v} = g_2^y$, then $u = g_1^x$ and $v = g_1^y$ since $\psi(g_2) = g_1$. This leads to:

$e(v^{\alpha}, \hat{u}) = e((g_1^y)^{\alpha}, g_2)^x = e(g_1^{\alpha y}, g_2)^x = e(g_1, g_2)^{(\alpha y) x} = e(g_1, g_2)^{(\alpha x) y} = e(g_1 ^ {\alpha x}, g_2^y) = e((g_1^x)^{\alpha}, g_2^y) = e(u^{\alpha}, \hat{v})$

AS stated above, this only works under the assumptions above, which are assumptions. If these are not correct feel free to leave a comment or edit.


Secure group chat with large groups I was reading in Whatsapp group chat the sender encrypts a key individually for each memeber. And everyone invalidates their key whenever anyone leaves the group.

Whatsapp also limits group size to 256 members, making the above feasible.

Can we do better? To support significantly larger groups? While maintaining end to end encryption?
Will we be able to still maintain other properties, like forward secrecy?

Can we do better?

Yes. See: On Ends-to-Ends Encryption: Asynchronous Group Messaging with Strong Security Guarantees.

To support significantly larger groups?

  Our results demonstrate that ART is practical for reasonably-sized groups, with key tree setup and message sending both taking a few milliseconds for groups of size ten and on the order of one second for groups of size 1000.

While maintaining end to end encryption? Will we be able to still maintain other properties, like forward secrecy?

The important property that we care about here is Post-Compromise Security (PCS), defined as:

  Moreover, some modern messaging protocols offer a property called Post-Compromise Security (PCS), sometimes referred to as “future secrecy” or “self-healing”. For PCS, even after Alice’s device is entirely compromised by an adversary, she may later be able to establish secure communications with others after a single unintercepted exchange.

These trees establish new group shared keys when any member joins or leaves the group, or when each member decides to rotate their key. In double-ratchet keys usually rotate after the first message from each user since the key changed, although some implementations, specifically Matrix' Olm, opt to be less noisy; re-keying every N-messages or after T-seconds.


Why unit vectors should be encrypted bit per bit in that case? At this work at section $2.2$ concerning a possible application for the BGN cryposystem the author points out that if you want to encrypt a unit vector $\overrightarrow{u_l}$ of size $l$ then the naive way is to encrypt each bit separately. And by following the idea of BGN the size of the ciphertext is reduced to $2\sqrt{l}$ from $l$. My question is why the naive way is to encrypt each bit seperately and not encrypt at once as a number in the specified group $\mathbb{G}$ as long as the value can let you efficiently compute the $DL$ as the discrete logarithm is needed for decryption as described at the original paper?

The answer can be found in the lecture notes you link to.  You quoted from Section 2.2 of the lecture notes; if you read to the end of Section, you will find (on the very same page) the following statement:

  This encryption of a unit vector has applications to “private information retrieval”; details are in the BGN paper [1, Section 4].

This suggests that you might want to read Section 4 of [1] (the paper that introduces the BGN cryptosystem).  I suggest you particularly read Section 4.2, the part labelled "A SPIR scheme".

That part describes a scheme for private information retrieval.  If you work through the details of the protocol, you will discover that it involves having Bob encrypt a number (the index of the database that he wants to read) using the scheme described in Section 2.2 of the lecture notes.

Encoding the number as an element of the group would be fine in many cases, but it would not work for that particular "private information retrieval" protocol.  So, there's your reason.  That should answer your question.


Is there a proxy re-encryption algorithm for Elliptic Curve ECIES? I was wondering if there is a way to perform proxy re-encryption for ECIES public-key encryption (i.e. given a message encrypted with Alice's public key, re-encrypt it using Bob's public key). Is that even possible?

In ECIES, the ciphertext is a pair:

$$rG, \text{Encrypt}_{h(raG)}(Message)$$

here:

G is the block generator point
aG is the public key that this is encrypted to (in this case, Alice's)
r is a random value
Encrypt is some symmetric cipher (the details aren't important)

What the proxy encryptor needs to do is convert this into:

$$r'G, \text{Encrypt}_{h(r'bG)}(Message)$$

Where $bG$ is Bob's public key, and $r'$ is a possibly different random value.

Surprisingly enough, this is possible, if the proxy encryptor knows the value $ab^{-1}$ (where $a, b$ are Alice's and Bob's private keys).  Note that just knowing the value $ab^{-1}$, without knowing either $a$ or $b$, does not reveal either key.

What the proxy encryptor would do is replace the ciphertext with:

$$ab^{-1}(rG), \text{Encrypt}_{h(raG)}(Message)$$

(that is, multiplies the point by $ab^{-1}$ and leaves the symmetric portion alone).

If we denote $r' = ab^{-1}r$, then we note that this is the same as:

$$r'G, \text{Encrypt}_{h(r'bG)}(Message)$$

And so is a valid ciphertext encrypted with Bob's public key.


Encypted comms between two parties with facilitating middleman Charlie knows both Alice and Bob. Alice wants to send a message to Bob. Charlie must at all times know that Alice is sending Bob a message but must never know the content of the message.

The message can go from Alice to Bob direct or via Charlie. But at no time should Charlie know the content of the message.

The solution I can think of is to use Signal protocol with Noise Pipes (like WhatsApp).

Is that approach ok? Is there a simpler approach to the problem?

Thanks

Yes, there is a simpler approach: radio. You could use a symmetric cipher--just take your pick according to your security needs.

Over VHF, for example, you set up a repeater for the signal between Alice and Bob, otherwise known as a relay station. In this case, the traffic is collected and forwarded by Charlie.

A repeater is usually set up to increase the working distance and maintain signal strength between two parties.

But one must be careful about sending encrypted radio messages. Doing so is often illegal, no matter your frequency band/modulation, depending on local/state/federal laws. Get informed before you try this at home.

The symmetric encryption method you choose--out of those available--might not matter that much in this scenario, but you now have other problems:  an integrity check, authentication, and jamming (otherwise known as denial). Furthermore, how will Alice know that her message was forwarded?

In practice, such a system may result in Bob getting two messages: first from Alice, then from Charlie, depending on atmospherics (even for VHF); that is, the occasional strangeness of wave propagation, which can result from many factors--some variable, some not.

By the way, one reason that sending encrypted radio transmissions is commonly illegal (even over a legal frequency band), even though it can be cheap and work very well indeed, is that this is an effective way to communicate while staying off of a collection platform.

For example, a VHF radio signal using a directional antenna on relatively low power from Alice to Charlie and then Charlie to Bob might make sense in certain situations.  One could even use a one-time pad.  Charlie then has no chance to break your traffic--if he ever had that in mind.  There are simple programs that send ciphertext from a GUI on your computer over an attached VHF radio.