Simple reversible algorithms that satisfies SAC

One simple approach would be, if your input/output size is $n$ bits, is to select a representation of $GF(2^n)$, and a random nonzero value $v$, and have your function be $F(u) = u \times v$ (where $\times$ is multiplication within $GF(2^n)$)

It operates on blocks of fixed size
It is reversible (by multiplying by the value $v^{-1}$)
It satisfies the SAC in this sense: for input bit $i$, and any output bit $j$, flipping bit $i$ of the input will flip bit $j$ of the output for almost exactly half, that is, $2^{n-1}/(2^n-1) \approx 1/2 + 2^{-(n+1)}$

Now, it doesn't satisfy the SAC for a fixed value $v$; for a fixed value, flipping bit $i$ will flip bit $j$ either always or never; so, it might not be the answer you're looking for (on the other hand, it may)


Strange modular expression in paper on group signatures

In this context $1/e_i$ (more commonly written as $e_i^{-1}$) stands for the multiplicative inverse of $e_i$ modulo the relevant modulus, which in this case is $\lambda(n) = \text{lcm}(p-1,q-1)$.  That is, $1/e_i$ is that value $f$ such that $f \cdot e_i = k \cdot \text{lcm}(p-1, q-1) + 1$, for some integer $k$.

Given the factorization of $n$, we can compute $1/e_i$ using the Extended Euclidean method.

We also believe that that $(C_2 \cdot a_0)^{1/e_i} \bmod n$ cannot be computed without knowing the factorization $n = p \cdot q$ (for general $C_2, a_0, e_i$); in fact, this is precisely the RSA problem.


Convert ciphertexts of one encryption scheme to another without decryption

I know of a proposal from Matsuo in 2007, called "Hybrid Proxy Re-Encryption", which allowed to transform PKE ciphertexts to IBE ciphertexts. This proposal is designed for a specific PKE and IBE scheme, not for generic ones. Note also that this is not what we usually understand by the term "proxy re-encryption", which is devoted to transforming ciphertexts from one key to another.

The only way to do what you ask with arbitrary schemes (e.g., OPE to Paillier) is to use fully homomorphic encryption. See these two answers (1 & 2) that could give you a hint of how to do this with FHE.


What, cryptographically speaking, is a "long message"?

Without the specific reference I can't be sure this is what you are talking about, but generally a "long message" attack is a way to defeat second preimage resistance with less complexity than expected.  It uses a time-space tradeoff to find a second preimage with complexity $2^{n/2}$ for a $n$-bit hash function (normally you would expect $2^n$).

In the simplest form, what you do is generate a message that is $2^{n/2}$ blocks long, which will consequently have about $2^{n/2}$ "intermediate" hash values (output from the hash function upon processing each block).  You store those hash values in memory, and then try repeatedly hashing random messages until you find a message $m$ such that $h(m)$ is equal to one of the intermediate hash values.  This will take about $2^{n/2}$ tries, since you have $2^{n/2}$ targets to shoot for.

At this point you can split the long message on that target intermediate value and "splice" the message $m$ into that place, and it will still produce the same final output.  What this effectively does, is find a collision somewhere in the interior of the message and replace that substring with the new colliding one.  Since collisions are generally easier to find than second preimages (because of the birthday paradox), this leads to an effective second preimage attack.  Particularly, it requires only about $2^{n/2}$ time and $2^{n/2}$ memory, instead of $2^{n}$ time.

However, this is purely an academic attack since most hash functions use the Merkle-Damgard construction to handle large messages, and it includes a block at the end which specifies the length of the message.  In the above attack the two messages will not have the same length.


What is the proper way to implement AES CTR with 128 bit nonce and 64 bit counter?

This will be the protocol: $C_{i} = AES_{k}(IV  + i) \oplus P_{i}$  where $i$ is 64 bit counter, $IV$ is $128$ bit nonce and $+$ is arithmetic addition modulo $2^{128} -1$.

Is this secure (confidential sense)?

Well, you didn't really specify the nonce to be random. If it is a serial number then it is obviously not secure at the next file uses the same block as what the other one started with.

Will there be collisions in the input block to the AES function since we have already populated the initial block, with random IV (Can modular addition of counter cause collision)?

If it is random then you don't really know what the distance is towards the next IV. If you are (rather) unlucky then it is less than $2^{64}$ and then the really big files could be in trouble as the last part of one file and the first part of another may use the same counter and thus key stream. So serial number: clearly not secure

Is this a standard way of doing AES CTR?

Generally the counter value and the nonce would use separate bits. You'd round up the number of required bits for the counter and use as many as possible for the nonce. Sometimes domain separation could also be encoded in one or more bits.

What is the proper way to check for overflow? Should I check whether initial block (treated as a big endian integer) equals to $2^{128} -1$ or only whether $i$ equals $2^{64} -1$ and then raise an exception?

In your scheme you'd not really know when the overflow happens. In the general sense you could simply test if the counter returns to zero, or calculate the amount of bytes and make sure that you keep below that value.

You could also derive a different key per file, then you can use all 128 bits for the counter.
Let's describe such a system. $K_F = {KDF}(K_M, \mathbb{nonce}_F)$ where each value is 256 bits. Then start the ${IV}$ / counter at all zero so you can just perform $C = E_{CTR}(K_F, {IV}=0, P)$ and $C_{total} = ({nonce}_F, C)$ where $P$ is the original file and $C$ is the encrypted file.


Where is the mistake in my RSA by-hand calculation?

Your $d$ is indeed incorrect. I get $d = 4235309647073$, using Wolfram alpha.

As to python, use the builtin pow function with a third argument equal to the modulus.

So

message = 6
encmessage = pow(message, 17, 6000029000033)
assert message == pow(encmessage, 4235309647073, 6000029000033)

which will apply a smart algorithm like those in answers to this question. Never compute the direct power first!


Is it possible to implement the Signal Protocol without a server?

Expanding from the whiteboard example as that is just a transparent central server.

This is not an issue although with a different model, you just need to decide which properties you care about.

Without a trusted entity maintaining the lookup of verified phone numbers to public keys, you will need to rely on another means. I recommend using the public key directly to effectively null out this layer while keeping it orthogonal such that lookups may exist in the future.
Without a trusted store-and-forward service you'll need to establish a rendezvous point such a DHT or wrap another chat protocol that knows nothing about Signal. Wrapping another protocol can solve (1) opportunistically, although the service (like Signal) may return keys it controls and is just as trusted and centralized.
If you do not have a store-and-forward service then the signed prekeys are redundant. This does not reduce forward secrecy, but it does require the 3DH handshake to occur before messages may be sent. So no 0-RTT semi-forward-secure messages.
If delivery is synchronous and ordered you can simplify double-ratchet.
You may use an anonymity network such as Tor to hide who is talking with whom. Each user could be their own ed25519.onion service. But if they are, then double-ratchet and 3DH are both redundant and we've got ricochet.im.

Social graphs and deniability depend on the above choices. I.e. ricochet.im hides the social graph great using onion routing; if you want better, you'll need a mixnet. Or if you forward messages over some existing service, they can see the social graph prove you communicate and record the ciphertexts forever to verify any revealed keys and plaintexts.

On another note: you might want to take a look at matrix.org's libolm, a double-ratchet implementation that does not assume server cooperation.


Is it possible to validate a Public Key in RSA?

There are two approaches to such a validation:

Test: you can look at the number and decide without involving the person who gave it to you.
Proof: The person who generated the number can also give you additional information that will convince you it is a correct RSA number.

There are no tests for RSA numbers.

There are proofs for RSA numbers, including "zero-knowledge" proofs. Zero-knowledge means that the person who generated the number can convince you it has two prime factors without giving you any information about what the two factors are.

A zero-knowledge proof can be interactive: you and the generating party exchange messages (akin to challenges/responses) that lead you to become convinced. It can also be non-interactive: its a transcript that convinces anyone who looks at it. Thus if the generating party gives you the number and the proof, you can forward that to anyone else and they too will be convinced. With interactive proofs, unless you are watching each message go back and forth and know that the two parties that are interacting are not colluding, you can't be convinced it is correct.


Why do block ciphers use key schedules instead of round constants? (Even-Mansour)

What would be wrong with just having a 256 bit key that you XOR into
  your input and then XOR into your output?

If I understand you properly, you split the 256 bit key into two 128 bit parts. This will be the whitening key that helps to resist exhaustive key search.

In term of round constant, it is adds asymmetry to the key and prevents slide attacks. However, you overlooked other attacks such as invariant subspace attacks for which you have to choose constants that eliminate weak key classes.

A related-key attack may remove the effect of the constant (key difference  eliminates the constant) but in real world, the adversary needs to have access to key generation to perform this attack.

I believe that the design of key-schedule lacks to solid proof. There was a paper in FSE18 about the mathematical proof of the AES-128 key schedule under related key attack. A solution was proposed using a better and lighter key-schedule without s-box or round constants, just permutation.

However, how to choose constants that prevent slide attacks? In other words, is there a proof that adding any constant will stop a slide attack?


Why random number used in RSA padding but not in AES?

They are different concepts and have different approaches. AES like any block cipher is a primitive and the encryption is performed by using the block cipher mode of operation. Like ECB,CBC,CTR,GCM,EAX...
The pkcs#7 padding or any other padding that is used to fill the last block to the block size with ambiguous remove, not designed for randomization. Even one can design a randomized padding mechanism it can affect at most 2 blocks without wasting the other blocks. Therefore not a good randomization point. Indeed, the CTR and OFB don't use padding at all.
The randomization ( probabilistic encryption) is achieved by using IV/nonce.
Since the insecure ECB doesn't use an IV, it doesn't have Indistinguishability under chosen CPA attack (Ind-CPA). This is the minimum requirement for modern Cryptography, but not enough. The other modes have IND-CPA.
Like other Authenticated Encryption modes, AES-GCM can have IND-CCA2. And we prefer the Authenticated Encryption ( with Associated Data (AEAD)) to use. The common modes are AES-GCM, ChaCha20-Poly1305, EAX, and CCM. TLS 1.3 standard has the AES-GCM, AES-CCM, and ChaCha20-Poly1305 AEAD cipher modes.
And note that Authenticated Encryption is a stronger notion, AEAD > IND-CCA.
One should note that IV/nonce is necessary but not sufficient for security. For example, the CBC IV must be more than a nonce, it must be unpredictable. For the CTR mode, the (key,IV) pair must never be reused ( similar to GCM mode since it uses CTR mode inside). There is a mode against the nonce misuse:
SIV (Synthetic Initialization Vector) mode, it called a nonce-misuse resistant authenticated-encryption.


Is this hash function almost XOR universal?

Is this hash almost-XOR-universal?

No.

Consider the two 1 block messages $M = \{0\}$ and $M' = \{2^{n-1}\}$.

We have:

$$H(M) = ((2\cdot 0 + 1)(2K+1) \bmod 2^{n+1}) /2 = K$$

and

$$H(M') = ((2\cdot 2^{n-1} + 1)(2K+1) \bmod 2^{n+1})/ 2 = K + 2^{n-1} \bmod 2^n$$

As $H(M) \oplus H(M') = 2^{n-1}$ has a nontrivial probability of being true, $H$ is not almost-XOR-universal.

Similar logic (using the two messages $\{0, 2^{n-1}\}$ and $\{2^{n-1}, 0\}$) will show that $H$ isn't even almost-universal.


Exactly what part of SIDH is proven to be NP-hard?

SIDH is believed to be quantum secure because the fastest known quantum attacks against it (which is based on claw finding algorithm) require exponential time with complexity $\mathcal{O}(p^{1/6})$.


How does RSA compute such enormous numbers?

Surprisingly, very basic algorithms which the children learn at the basic schools are used. For instance:

http://www.wikihow.com/Do-Long-Multiplication

You can find a similar algorithm for sum, sub and division. Try to ask google for: "division on paper"

The "power of" is little tricky. In cryptography you don't really need the "real power of". Instead you need:

(a ^ b) mod c

It is easy to compute a^(power of 2) mod c

a * a mod c= a^2 mod c
(a^2)^2 mod c= a^4 mod c
(a^4)^2 mod c= a^8 mod c
...
(a^512)^2 mod c= a^1024  mod c

And if you need a^5

(a^5) = a^2 * a^2 * a

thanks to "mod c" you keep the numbers no higher than c.

For example:

c = 10

2^2 = 4
2^4 mod 10 = (4^2) mod 10 = 16 mod 10 = 6
2^8 mod 10 = ((4^2)^2) mod 10 = (6^2) mod 10 = 36 mod 10 = 6
2^16 mod 10 = (6^2) mod 10 =....

etc..

There are many tricks how to make the calculation faster. For example, Montgomery multiplication algorithm is often used for that. But even without those tricks the implementation would be fast enough. I would estimate RSA instead of 0.2s would take 5s or so.


What is actual difference between POODLE and BEAST?

BEAST was indeed an attack on CBC mode with predictable (in fact known) IV in SSL3 and TLS1.0, because those protocols used the last block of the previous record, which (usually) has already been sent and seen by the adversary, as the IV for the next record.

Record splitting blocks this by encrypting a (mostly) fixed stub record (at most one byte of data, plus HMAC and padding) using the known IV, producing quasi-random ciphertext, and in the same transmission sending (nearly) all the data in a second record using as IV the last block of the first record which is now not predictable. OpenSSL did 0/n splitting back in 2002 in response to an observation of this flaw by Rogaway, but it was widely disabled for interoperability; pretty much everybody else did 1/n splitting rapidly (weeks or months) in response to BEAST in 2011. The former is described adjacent to the document you linked at https://www.openssl.org/~bodo/tls-cbc.txt

See also https://security.stackexchange.com/questions/17080/is-there-a-way-to-mitigate-beast-without-disabling-aes-completely
POODLE is not an attack on IV at all; it is a padding oracle attack on the padding used in SSL3 (and it turned out some debatably defective TLS1.0 implementations also), hence the acronym Padding Oracle On Downgraded Legacy Encryption. Because POODLE has nothing to do with the IV, predictable or otherwise, fixing the IV has no effect on it.

See canonical (and ursine) https://security.stackexchange.com/questions/70719/ssl3-poodle-vulnerability/ and perhaps (mine, but nearer) How does padding oracle attack work with bytes larger than possible length?


RIBE Scheme Implementation - How to encrypt message

Given that the authors (as any sane person should¹) use multiplicative notation for all of the involved groups, "$\cdot$" simply represents the group operation in the target group $G_2$.

It does not seem to be explicitly specified as far as I can tell from skimming the paper, but this implies that the message space of the encryption scheme is exactly $G_2$, meaning that we always have $M\in G_2$. So there are no "chunks" involved.

If you want to encrypt a message directly with the scheme, this means that you will need to encode it as a $G_2$ element. If your message is too long for that, you will need to use one of the standard domain extension techniques, such as using the RIBE as a KEM in a hybrid encryption scheme.

¹This is a hill I'm willing to die on.


Use of the IV for the CBC Block Cipher in TLS1.2

No the IV doesn't get encrypted. The IV is a random vector to make sure that the ciphertext is not identical for identical plaintext. This would leak information to any eavesdropper. It needs to be unique - and in the case of CBC, indistinguishable from random to the eavesdropper ("unpredictable") - but not confidential.

As the IV is separate from the ciphertext, it does not affect the padding. However, the RFC has this information:

  The padding length MUST be such that the total size of the
        GenericBlockCipher structure is a multiple of the cipher's block
        length.

The IV is included in this structure. This is still correct as the IV is specified as being exactly the same size as the block size (for CBC):

  the IV length is of length
        SecurityParameters.record_iv_length, which is equal to the
        SecurityParameters.block_size.


Commutative Hash Function for Password Challenge?

If you are storing $h_1(password)$ and I break into your database, I will simply sort all the hashes I find. The one that appears most often will be $h_1($"123456"$)$, closely followed by $h_1($"password"$)$. In other words: you're storing unsalted hashes.

This is why you use special key derivation functions like scrypt and not plain cryptographic hashes on passwords.

If you are doing a man-in-the-middle attack, you generate your own key $k$ and send it to the user, who replies with $h_2(k, password)$. You know $k$ (this is still the case if you use a "trust-less protocol" to agree on $k$) so you can now try $h_2(k, x)$ for all $x$ in the 10 million most common passwords list at your leisure - even without breaking into the server.

If we're talking about key-based authentication, where collisions are unlikely to be a problem, there is an authentication protocol that uses a commutativity property a bit like you mentioned: Schnorr ZK proofs.


After ECDH with Curve25519, is it pointless to use anything stronger than AES-128?

The reasoning is wrong, because the scaling of attacks on AES is qualitatively different from the scaling of attacks on X25519.

A successful multi-target attack on a system using AES-128—that is, an attack that recovers one of many keys—can cost much less than $2^{128}$ evaluations of AES-128.  Specifically, using Oechslin's rainbow tables, and on a machine parallelized $p \geq n^2$ ways, the expected cost of recovering the first of $n$ keys is $2^{128}/n$, the expected time is that of $2^{128}/np$ sequential evaluations of AES-128.  The expected cost of breaking all of the $n$ keys is still close to $2^{128}$, but in a real network of users, compromising one of them may be enough to compromise many of them.

In contrast, a successful attack on X25519 is expected to cost at least about $2^{128}$ bit operations using the best known strategy, even if it is a multi-target attack.  The expected cost of recovering all of $n$ keys is about $2^{128}\sqrt{n}$ bit operations, so there is an advantage to batch multi-target attacks, but the cost to recover the first one is still an insurmountable $2^{128}$ bit operations.

If you say that AES-128 has a ‘128-bit security level’, then you should consider X25519 to have a much higher security level.  But I don't think that's reasonable.  Rather, I think it is reasonable to say X25519 has a ‘128-bit security level’ and AES-128 has a much lower security level.

If you must use AES, then use AES-256 unless you have an overwhelming budgetary constraint preventing you from doing so.  If you don't need to do economics, don't let the adversary do economics either.

Consider using the simpler faster safer Salsa20 or ChaCha if what you really need is an IND-CPA cipher and you were going to use AES-CTR or AES-CBC or something instead.  Consider using authenticated encryption unless you have a reason not to—really, consider using NaCl crypto_secretbox, just like NaCl crypto_box uses internally with the outcome of an X25519 key agreement.


Ed25519 signature verification as described in RFC 8032

If you look at the key generation

Prune the buffer: The lowest three bits of the first octet are
cleared, the highest bit of the last octet is cleared, and the
second highest bit of the last octet is set.

This used to make sure that the key is not in the small groups, those have order 2,4, and 8.
If you use

$[8][S]B = [8]R + [8][k]A'$.

then if the public key is in a small order, sides will get the identity $\mathcal{O} = [8][S]B$ and you can detect with this. This is key validation.
But, it is not your problem right? Maybe the other side chooses the key deliberately instead of using the recommendation. Then just use $[S]B = R + [k]A'$. but not required. Better check it.


Can a hard drive store clear text data that is physically impossible to retrieve?

The normal way is to keep secret data in volatile static RAM (i.e. 6 transistors per bit, like in current CPU caches, not with capacitors like in DRAM). When the power is cut, the data is gone in a matter of microseconds. The HSM contains a small battery to keep the RAM up and running for up to a few weeks. The battery also powers an array of sensors, e.g. on temperature, light, physical integrity of the covering and so on. If anything goes amiss, the system automatically shuts down the power, and the keys are gone.

So the trick, really, is not to store the data "in an hard drive, permanently".

An amusing consequence is that if an HSM is unpowered for too much time, the keys can be lost. Pro-tip: when you ship an HSM to a factory in China, label it as "a network card". Otherwise, customs will keep it around for a month, and the keys will be lost.

The above is valid for HSM and payment terminals. Smart cards, on the other hand, employ other tricks, which are undocumented (and most of them are trade secrets).


Do (should) services where the customer has to provide a public key,
  check this public key for weaknesses? What kind of weaknesses could a
  key be tested for?

I'm pretty sure that there's no easy way to find out if a public key has been generated safely without some sort of brute-force attack.

Ultimately I think it's up to the creator of the public key to make sure that the generated key has been created in an orderly fashion, i.e. by using a secure CSRNG. So services should probably not check public keys provided by customers for weaknesses.

The three tests that you have listed are generally good ways to check for possible weaknesses (if you would want to do so). Your second point though (The key is not a known compromised key (public databases?)) might be very inefficient, depending on how large such a public database could be.

  How would you test for these?

The bit length is appropriate for the algorithm the key is used for (best practices?)

A list of recommended key lengths: BlueKrypt.

The key is not a known compromised key (public databases?)

If the database consists of the factors (in case of RSA), you could just try to divide a public key with all these factors and see if it results in a whole number. If the database only consists of public keys (in case of RSA), you could use the Euclidean algorithm and go through all keys in the database.

The key is not generated using a bad random generator (how would you test this?)

Unknown, unless you know which tool was used to generate the key.


Is this an acceptable authenticated encryption?

This is basically a description of a protocol, I'll just go over the cryptography related points that you've raised.

At least the nonce is missing from the calculation. Just to be sure I would include the entire counter value used in the CTR encryption.
64 bit of MAC output should be OK, both NIST SP 800-107 Revision 1 and NIST SP 800-38B define 64 bit of hash output as acceptable. See NIST SP 800-107 table 2. If less bits are used additional security proof would be required.
It is possible to go for an AES based MAC instead (AES-CMAC). AES is likely to be faster - especially if encryption is currently not the dominating cost; this depends on the deployed hardware and runtime environment of course.
That's hard to tell without taking the complete protocol into account. Most of the time the symmetric algorithms are not the hard part of the protocol - authentication and key management are much harder parts to get right. This is why choosing TLS should be preferred.

There are two side channel attacks that are often forgotten when creating an online protocol.

Timing attacks are particularly dangerous, especially during the authentication/session key derivation phase.
Ciphertext length based attacks are particularly dangerous on the application level, including the authentication phase (e.g. of username/password).

Please take both into account when designing any secure transport protocol.


Why not just generate random strings for one-time password (OTP)?

Just using random strings is simple and often reasonable solution. However, if you have significant customer base, it can become too expensive, because all of those random strings need to be stored.

But in short, these more complex schemes are mainly for reducing storage requirements and amount of entropy needed. Note: I am partially building this reply on previous two replies.

Reducing required entropy and storage requirements

Just generating random strings means need to generate and store lot more random bits than many of more well thought OTP mechanisms. For instance, S/KEY needs to generate and store just one value, even there can be e.g. one hundred passwords, thus reducing storage costs to one (theoretically) up-to one hundredth of random strings. Because less random bits (entropy) are needed, the OTP mechanism is easier to test and validated.

(Note: to handle transitions and expirations smoothly, usually more than one value needs to be stored.).

I agree to some degree with md_1976, however, I disagree on amount of information stored on the server. Time-based OTP schemes typically still need some information on user account, like serial number of user's authentication device (hardware device). In case there is software implementation of time-based OTP, server likely needs to know the public key of user's device or possibly the server and device needs a shared secret. One possible issue with time-based OTP schemes is that they tend to require special client-side software or hardware. One the other hand traditional OTP schemes can work even just via e.g. letter and phone network.

In time-based scheme with client side hardware device, typical information to store per account could be serial number and or other identification codes of the device.

Sizes of stored values

For purposes of comparing cost. (The possible other values e.g. account id or timestamps not considered.)

Original S/KEY (RFC 1760) - this is based on MD4 hash function, which is considered broken. Not recommended to be used.
OTP (RFC 2289), based on MD4/MD5, or SHA1. 64 bits storage needed, per OTP key.
HOTP (RFC 4226): Shared Secret is 128-bits or more (recommended 160-bits).
TOTP (RFC 6238): Uses same sized shared secret as HOTP.


Is Strong MAC stronger than existential unforgeability?

I assume that by a "strong MAC" you mean that it is infeasible for an adversary to also find a different MAC tag on a message which has been tagged. Any deterministic MAC (with canonical verification) is a strong MAC, but it is certainly not the case that every MAC is a strong MAC. Thus, indeed, there exist secure MAC schemes (that are existentially unforgeable) but are not strong MACs, meaning that this is a strictly stronger notion (by definition, a strong MAC is existentially unforgeable so the question is just whether it's the same or strictly stronger as a notion). Note that in order to achieve CCA security you need a strong MAC and thus in the context of encrypt-then-authenticate, this is indeed needed. It is possible to define a weaker type of authenticated channel for which it would not be necessary, but typically it is required.

For those not sure what a strong MAC is, see the following pasted excerpt from "Introduction to Modern Cryptography":


Your proposal is more or less what NIST SP 800-90A describes as "Hash_DRBG". From a pure cryptographic point of view, there's nothing bad with it. A few remarks can be made from a more engineering standpoint:

It's not very fast. SHA-512 is a reasonably fast hash function on 64-bit architectures, but that statement is about the amount of input data that SHA-512 can absorb. Each SHA-512 instance processes input data as blocks of 128 bytes, but outputs only 64 bytes. One can hope for, possibly, about 150 MB/s of output on a recent x86 CPU. By comparison, AES/CTR (with the dedicated opcodes) will go at 5 GB/s. Moreover, on 32-bit architectures, especially small ones (microcontrollers), SHA-512 is terrible. AES/CTR (on systems with a hardware implementation of AES) and ChaCha20 (on all others) will be a better bargain.
If you concatenate a counter, a 64-byte seed, and "additional data", and the total length exceeds 111 bytes, then each SHA-512 instance will require the processing of several blocks (111, not 128, because of the SHA-512 internal padding), and performance will further decrease. It would be better to first process the seed and the additional data into an aggregate 64-byte value (e.g. with a SHA-512 call), and use that aggregate value along with the counter into SHA-512/CTR.
"Userland" PRNG have some potential security issues. For instance, a call to fork() (on a Unix-like system) will duplicate the internal state; the parent and the child will then produce the same pseudorandom output from their shared state. A similar point can be made about virtual machine snapshots. Generous use of an uncloneable random source can help mitigate such issues (e.g. RDRAND on recent x86 CPU). Going through the kernel (/dev/urandom or equivalent) can help with that: the kernel is resilient to cloning by fork(), and it has direct access to the hardware, allowing to use random sources such as RDRAND, which are tricky to invoke from .NET code.
Assuming an attack that can compromise the internal state, the attacker will learn enough to not only predict the next pseudorandom bytes, but also previously generated output, by "rewinding" the counter. If you do not use fresh randomness, a compromise of future output, under that scenario, is unavoidable; however, forward secrecy should be maintained: even after full memory compromise, past generator output should be forever out of reach. Such a property can be obtained by "ratcheting" (in simple words, replacing the current seed with a one-way hash of it). If you look at NIST SP 800-90A, this is what happens at the end of the Hash_DRBG_Generate process, after producing the requested output.


I would pick e) none of the above. None of those modes offers integrity protection, so unless integrity is handled elsewhere, your application is wildly insecure. An attacker could modify bits in transit and do nefarious things.

Of the three, CFB and CTR are the worst for the application and should be very easy for an attacker to mount successful attacks, changing commands being sent to the server that are properly formatted. CBC would take a little more creativity, but shouldn't be too hard for an intelligent attacker.


Witness-extended emulation is a more robust notion of knowledge soundness that avoids subtle problems when the proof of knowledge system is used inside of bigger protocols.

For example, suppose you have a two-party protocol between A and B where at some point A provides a PoK for some statement x. (So the PoK is used as a sub protocol inside this bigger protocol.)

Now, to prove that the protocol is secure you want to build a simulator S that simulates a corrupted A. To do so, it produces a view that is the view of A in the protocol, which includes the transcript of the PoK.
Also we can assume that this simulator needs to extract the witness from the PoK (in almost all cases the simulator needs to do so: intuitively, it seems that otherwise this PoK would be kind of useless).

Thus a naive simulator could:
1) Run with A and act as a verifier so to get a transcript of the PoK
2) If the transcript is valid, run the extractor E.

Now, the problem is that for (standard) knowledge soundness we have that the extractor is an expected polynomial time machine that outputs a valid witness and runs in $poly/(p-k)$ where $p$ is the probability that A outputs a valid proof and $k$ is the knowledge error (very roughly speaking, the probability of convincing the verifier by sending random messages).

The problem is that if we compute the expected running time of the simulator S we have that it is at least $p \cdot poly/(p-k)$, which might not be expected polynomial time!

Luckily, Lindell (https://eprint.iacr.org/2001/107.pdf) showed that if you have knowledge sound then you can get witness-extended emulation. So we don't have to worry about.

To summarize, whenever you want to use your PoK inside a bigger protocol it is more convenient to rely on witness extended-emulation (less troubles with the proof of security). While, if the PoK is used stand-alone then both the notion of security are fine.


How does Naver Line PC client obtain private key for end-to-end encryption (letter-sealing)?

Converting a lengthy comment exchange to an answer:

  How does Naver Line send my private key stored on my phone to the PC client?

LINE has provided a technical whitepaper which described how message end-to-end encryption was done.  https://scdn.line-apps.com/stf/linecorp/en/csr/line-encryption-whitepaper-ver1.0.pdf  Since that whitepaper provides technical details about the communication protocols and encryption algorithms integrated into LINE’s messaging and VoIP platform, and since repeating what they wrote in their whitepaper doesn't make sense, I just have to ask: What information within that PDF didn't you understand? Why doesn't their own information satisfy your needs?

  The whitepaper does not explain how the PC client obtains the private key from the mobile device. Please suggest if you find it in the whitepaper

What you describe in your Q (a code that shows on PC which you have to enter on mobile) is verifying your identity on the PC version of LINE.

Your PC version then gets all the needed data via their servers. As the PDF explains on page 11 (4.2.1) In order to be able to send encrypted messages, each LINE client application generates a Letter Sealing ECDH key pair, and saves it securely in the application’s private storage….

So, your PC doesn't simply get your mobile keys and use those — it uses it's own keys to securely exchange data (incl. what's needed to decrypt other encrypted messages).

Since your question describes the authentication/authorisation process of setting up a new client device, and since the "keys" part you ask about is described in their PDF, it's pretty unclear to me what exactly you're asking since everything you mention is already be covered by their whitepaper (as well as their website, which contains the same infos using layman's terminology).

  Are you saying that the the private key on my phone is not private as Line can retrieve it for purposes or Line keeps my private key on Line server for their future use. This is not E2EE from my point of view and contradicts to the information on whitepaper on page 16.

No, I'm saying that they use your individual device's keys to securely exchange secrets from device to device (… as the whitepaper explains).

Mobile = keypair 1, PC = keypair 2, etc. Using those public key encryption keys, it's very well possible to exchange secrets (like private keys) between your devices in a secure E2E manner. In case of doubt, read up on how public key encryption works.

  Line PC could sync previous messages from mobile device even when the mobile is offline. It can’t be done by using different keys

Because those encrypted messages are stored on their servers.

Note that while you enter the PC authorisation/authentication code (they call it "verification code") into mobile, you not only authorize your PC but are also online — which is a perfect time to sync keys between devices, so that you can read your older messages on your new device.

Once this initial key sync is done (should take not more than a few KBs, so it's done in a few secs while you're authorizing your new device), you are able to read all old messages on your new device even when all your other devices are offline from that moment on.

Actually, that's similar to how 99.999% of the secure E2E messaging apps do it when they offer multi-device access to old/stored encrypted messages stored on a 3rd-party server.

Besides all that, of should be noted you're asking about (what they call) "Letter Sealing", which  uses unique, user-specific encryption keys which allow users to safely and securely send messages to one another. Their user-account specific keys are more restricted (according to their website) which is one of the reasons their help center mentions Can I use the same account on more than one device? With the smartphone version of LINE, the same account cannot be used on multiple devices. Only one phone number or email address can be used to verify one account per device. If you register the same phone number on a different device, the account on your previous device will automatically be deleted and you will no longer be able to use it. You can use the same account on the PC and iPad versions of LINE by logging in with the same email address.

Now, please don't get me wrong, but it may be advisable for you to read up on how public key encryption generally works, before diving into things which might be hard to grasp when not knowing which practical solutions public key encryption can offer in alike scenarios.

Nota Bene: This answer is solely based on the PDF documentation and website information which has been made available to the general public by the specific messaging service provider. The answer is not meant to indicate or imply a full-fledged assessment of theoretical and/or practical security. The answer should therefore not be interpreted or referred to as such a security assessment.


AES encryption using a Diffie-Hellman key exchange

There is nothing related to passwords in AES. AES uses 128-bit keys, i.e. sequences of 128 bits. How you come up with such a key is out of scope of AES. In some contexts, you want to generate these 128 bits in a deterministic way from a password (and possibly some publicly known contextual data, like a "salt"); this is a job for password hashing. In other contexts, in particular the one you are talking about, there is no password.

In Diffie-Hellman, computations occur modulo a big prime p, and the resulting shared secret is an integer modulo p, i.e. a value ranging from 0 to p-1. This value has some "structure" so you should not truncate it blindly. The "safe" way is to apply a hash function on an encoding of that value, for instance SHA-256. The hash function output is then what should be used as key (with possible truncation to get the proper length; at that point, this is safe). There are standards which describe such a process in full details.

Of course, you are in the process of reinventing your own homemade kind-of-SSL, and that is a thoroughly bad idea in general (unless you are doing it for pedagogical reasons, e.g. as homework). A really secure protocol will need key exchange, proper symmetric encryption, integrity checks and at least one-sided authentication, so you will have to assemble at least three cryptographic algorithm. Every single detail can doom your security, both in the design and in the implementation. This is hard. It took two decades of hard labour, from hundreds of the best cryptographers, to come up with a decently secure version of SSL.

So there is a standard, it is called TLS (the "standard" name for SSL).


What is necessary for generating an elliptic curve?

Let's suppose that you want to generate a classic $n$-bit curve in a prime field, with the complete curve order being prime. The process goes about thus:

Get a prime $p$ of size $n$ bits. The curve will be defined in the field of integers modulo $p$. For all we know, you can use $p$ to have a "special form" that promotes more efficient computations (e.g. $p = 2^n - c$ for a very small value $c$). It is not proven that special-form $p$ do not weaken the curve, but no such weakness is known. Alternatively, if you worry about unknown attacks, select a random $p$.

You may want to make sure that $p = 3 \pmod 4$ so that square root computations modulo $p$ are easy.
Generate a random non-zero integer $b$ modulo $p$ and count the points on the curve of equation $Y^2 = X^3 - 3X + b$. If that number is not prime, start again with a new $b$, until a prime order is found.
The prime curve order is $q$. Compute the trace which is $t = p + 1 - q$. If $t = 0$, then you were very unlucky and you got an anomalous curve; go back to step 2. If $t = 1$, then you were very unlucky and you got a supersingular curve; go back to step 2.
The curve embedding degree is the smallest integer $k ≥ 1$ such that $q$ divides $p^k - 1$. If $k$ is very small then Weil or Tate Pairing can reduce discrete logarithm on the curve to discrete logarithm in the multiplicative group of invertible element in the finite field $\mathbb{F}(p^k)$. With a super-large curve size $n ≥ 2048$ this would not even be an issue, but if you want to be really sure, just check all values of $k$ from $1$ to $100$ (that's what ASNI X9.62 recommends). If the embedding degree is too small to your taste, go back to step 2.

And voilà! you have your own curve.

Steps 1, 3 and 4 above are simple enough to implement with any language that has some support for "big integers" (either natively or with some library). Step 2, on the other hand, is quite complex to do and will be substantially slow; it uses Schoof's algorithm. You'd better use an existing implementation.

There are various additional details that you may want to mind, such as taking care of having a twisted curve which is also of prime order. Read up on Brainpool curves for some guidance here. You may also want to forego classic Weierstraß curves for the more fashionable Edwards curves, which allow for implementations that are somewhat faster, and easier to do properly.

But really, you should first question the wisdom of generating your own curves (because this will basically kill off any interoperability), and also of using curves of such overblown size (which will hurt performance very badly for no practical security gain).


You just have to do some simple algebra.

$$E^x \cdot F^y$$
$$(M^{e_1})^x \cdot (M^{e_2})^y$$
$$M^{xe_1} \cdot M^{ye_2}$$
$$M^{xe_1 + ye_2}$$

Well, what is $xe_1+ye_2$?


How practical is proxy re-encryption for AES?

Proxy re-encryption schemes are entirely practical. This is certainly true for AES symmetric encryption, as the proxy does little more than decryption with key 1, followed by encryption with key 2. This is called the "Naïve Way" in this lecture.

Now if PRE is suitable for a specific uses case is an entirely different matter. It depends on how secure the proxy itself is. If you require additional security in the PRE protocol itself you may have to go for a protocol that uses asymmetric encryption primitives.

Beware that a proxy more or less implies communication over insecure networks. If man-in-the-middle attacks are applicable then you should add an authentication tag to your messages.

More detail is required to answer your question for a specific use case.


There exist many standards which describe a lot of padding modes and security protocols. If you're new in that field, I strongly recommend you to study the family of PKCS standards which are the reference in the domain. There also exist other distinct standards depending of very specific application fields (Banking, mobile, Cloud, Embedding ... or Global Platforms).

Briefly, as you've certainly observed the RSA primitive is based on modular exponentiation and this operation is homomorphic in the sense that if someone knows two ciphertexts $c_1=m_1^d$ and $c_2=m_2^d$, then he can immediately deduce : $(m_1.m_2)^d= c_1.c_2=c$.
This is the essential reason to break this "homomorphism", by adding inside the plaintext some hash or other techniques.

Other security protocols allow an attacker to interact with an oracle to prove the security of the scheme. Then randomization can be included in some cases to prevent the attacker from deducing any bit of information about the plaintext when she is given the ciphertext. The subject is very vast.


First you should know that Elgamal encryption and signature security is based on DDH problem (Decisional Diffie Hellman) which is tractable in some groups that CDH problem is believed to be hard (Computational Diffie Hellman). As in the case of $\mathbb{Z_q}$ in which CDH is believed to be hard but DDH is apparently tractable.

Let $p = 2p_1 + 1$ where both $p$ and $p_1$ are prime. Let $Q_p$ be the subgroup of quadratic residues in $\mathbb{Z_p}$. $Q_p$ is a cyclic group of prime order itself in which DDH assumption is believed to be hard. This group and some other groups in which DDH problem is intractable are mentioned in this paper by Dan Boneh.

Any randomly chosen primitive element in $\mathbb{Z_p}$, say $g$, to the power of two ($g_1=g^2$) is a 'safe' generator for the subgroup of quadratic residues in $\mathbb{Z_p}$ (it is defined above as $Q_p$). A primitive element of $\mathbb{Z_q}$ is an element which are relatively prime to $p$. ($gcd(g,p)=1$)


Using encryption schemes for identification

Well, that would work, but identification is not enough for SSL.

You would need to make the PKE scheme one-way against CCA1 attacks. $\:$ (On the

other hand, it wouldn't need any semantic security.) $\:$ Sending back H(S') would change

the required security notion to one that's even farther from what's been studied.

You could use a tag-based PKE scheme that is one-way against tag respecting CCA2 adversaries to allow the private key holder to also authenticate data to the verifier, which would be enough for SSL. $\:$ (Although it would take 2 messages from the server and 1 from the client, rather than just 1 each.) $\:$ Also, hash-based signature schemes using fractal trees don't necessarily have a limited number of signatures.


What are the differences between these AES ciphers?

CTR mode aims at confidentiality only; GCM additionally aims at integrity (catching attempts to forge or modify a message by one not holding the key, nor having some form of access to a device holding it).

The numbers 128, 192 and 256 are the key size in bits. 128 bits of key is secure enough for most purposes; 192 (or more) is enough for all purposes, except when there is a regulatory requirement for even more. AES192 (resp. AES256) is slower than AES128 by roughly 20% (resp. 40%).

Chacha20-Poly1305 is functionally comparable to AES128-GCM (giving confidentiality and integrity), but is easier to implement securely and efficiently, especially without AES support in hardware.


ElGamal encryption of concatenated messages

We'll consider the additively homomorphic variant of ElGamal encryption, in a finite group with generator $g$ of prime order¹ $n$.
The private key is a random secret integer $d$ drawn uniformly randomly in $[0,n)$. The public key is $q\gets g^d$.
Encryption for integer $m$ goes:

Draw a random secret integer $k$ uniformly randomly in $[0,n)$
Compute $r\gets g^k$ and $s\gets g^m\cdot q^k$
Output ciphertext $(r,s)=c$ as the result of encryption of $m$, noted $E(m)$.

Decryption of ciphertext $(r,s)=c$ goes

Check that $r$ and $s$ are in the group
Compute $a\gets r^{n-d}\cdot s$
Find integer $m\in [0,n)$ with $g^m=a$. This requires tractable work for small $m$, using e.g baby-step/giant-step. For large $m$, we assume some oracle solves that problem when we write $D(c)$.
Output $m$ as the result of decryption of $c$, noted $D(c)$.

Note: Encryption $E$ is not a function. $D$ is one.
When $c=(r,s)$ and $c'=(r',s')$, we'll note $c\cdot c'$ for $(r\cdot r',s\cdot s')$; and $c^u$ for $(r^u,s^u)$.
It's easy to show that

if $0\le m<n$, then $D(E(m))\,=\,m$ [whatever $k$ was drawn by $E$]
$D(E(m)\cdot E(m'))\,=\,(m+m')\bmod n$
For any integer $u$ it holds that $D(E(m)^u)\,=\,(m\times u)\bmod n$ [where $\times$ is integer multiplication].

In the following, we assume the $c_i$ have been independently computed as $E(m_i)$ for $i\in\{1,2,3\}$; $m_2$ and $m_3$ are in $[0,2^{32})$; definition of $m_2\mathbin\|m_3$ as $m_2\times2^{32}+m_3$; and $n>m_1$, $n\ge2^{64}$.

(Given the value of such $c_i$) is it possible for the encrypter to prove with a zero-knowledge proof that $m_1\,=\,m_2 \mathbin\| m_3$?

Yes, if the encrypter/prover holds the private key $d$: define $c\gets{c_1}^{n-1}\cdot{c_2}^{(2^{32})}\cdot c_3$, and present any skeptical with a Zero-Knowledge Proof that $D(c)=0$ [see next paragraph]. Argue $D(c)=0$ proves $-m_1+m_2\times2^{32}+m_3\bmod n\,=\,0$, thus $m_1\,=\,m_2\times2^{32}+m_3$. The computation of $c$ won't be too tedious, for computing ${c_2}^{(2^{32})}$ requires computing a mere $62$ squares in the group, while ${c_1}^{n-1}$ requires at most $2\left\lfloor\log_2n\right\rfloor$ squares and less multiplications, using a standard method of exponentiation.
There remains to make a Zero-Knowledge Proof (ZKP) that $D(c)=0$; that is, with $c=(r,s)$, that it holds $r^{n-d}\cdot s\,=\,g^0$; equivalently, that $r^d=s$. The prover is assumed to know $d$, an can check this directly. The ZKP aims to convince the verifier knowing group elements $g,q,r,s$ that the prover knows $d$ such that $g^d\,=\,q$ and $r^d\,=\,s$. This the Chaum-Pedersen proof of equivalent discrete logarithms, explained there and there.
That should convince a rational verifier well versed in math. Good luck with that line of argument facing a random citizen fearing there was fraud in an election.

If the encrypter/prover does not hold the private key, but controls or keeps the $k_i$, there ares ways too.
A simple way is that the encrypter/prover generates $k_1$ as $k_1\gets k_2\times2^{32}+k_3$, rather than randomly. This ensures $c_1\,=\,{c_2}^{(2^{32})}\cdot c_3$, which is trivial for anyone to verify. That relation itself allows to prove this choice of $k_1$ [on top of the assumed $m_1=m_2 \mathbin\| m_3$] does not weaken anything. Even simpler, $c_1$ can be computed directly as $c_1\gets{c_2}^{(2^{32})}\cdot c_3$.
Computing and revealing $k\gets k_2\times2^{32}+k_3-k_1$ also does the job: it allows to check $c_1\cdot(g^k,q^k)={c_2}^{(2^{32})}\cdot c_3$, which conclusively proves $D(c_1)\,=\,D(c_2)\mathbin\|D(c_3)$. But I pass at proving my intuition there's nothing useful revealed, and I would not say it's a true ZKP.
But that can be turned to a true ZKP thru the Chaum-Pedersen proof of equivalent discrete logarithms: with $c=(r,s)$ defined as ${c_1}^{n-1}\cdot{c_2}^{(2^{32})}\cdot c_3$, the ZKP aims to convince the verifier knowing group element $g,q,r,s$ that the prover knows $k$ such that $g^k\,=\,r$ and $q^k\,=\,s$.

¹ That is: the group has $n$ elements $g^m=\underbrace{g\cdot g\ldots
g}_{m\text{ terms}}$ for $m$ in $[1,n]$, with $g^n$ the group neutral $1$. For security, $n$ is usually a large prime. A simple example would be a Schnorr group.


When using Curve25519, why does the private key always have a fixed bit at 2^254?

Curve25519 was designed to take advantage of the Montgomery ladder, which combined with Montgomery curves forgoes the $Y$ coordinates, is side-channel resistant, and enables public keys to be any 255-bit string. The ladder looks something like this (pseudocode):

Q[0] = P;
Q[1] = 2*P;
for(int i = log2(exponent) - 2; i >= 0; --i)
{
  Q[ bit(exponent, i)] = 2*Q[ bit(exponent, i)];
  Q[!bit(exponent, i)] = Q[0] + Q[1];
}
return Q[0];

You might notice the format of the loop: the counter is initialized with the index of the most significant bit of the exponent (i.e., the private key), and goes down to 0.

In practice, the first step of the ladder will be to find the most significant bit of the exponent. This is not hard, of course, but doing so may leak, through timing, information about the most significant bits of the exponent: exponents with bit 254 set to 0 will run faster than with that bit set to 1. This can lead to real problems.

Curve25519 completely avoids this problem by always setting the most significant bit to 1. This way, the loop always has the same amount of iterations, and no timing information can accidentally be leaked by the variable iteration count.


Formally, a signature scheme is broken, as soon as you can generate a message-signature-pair that you were not given before.

Thus, generating a large bunch of pairs of (random) messages $(m_1,m_2)$, and requesting a signature for one $(m_1)$ of them  and verifying if the signature also verifies the other message is a strategy that will yield you a new message-signature-pair $(m_2,s_1)$ rather sooner than later.

Now if you want to make an impressive demonstration of what the above means, you could just generate a large bunch of end-entity X.509 certificates (only differing by the serial number?) and a large bunch of X.509 intermediate CA certificates. The signer will be the CA which only issues end-entitiy certificate by signing the hash of the certificate. Thus your messages become the hashes of the certificates (which are computationally indistinguishable from random strings) and rather sooner than later you'll get a signature for an EE certificate that also verifies for one of the intermediate CA certificates and thus you have successfully forged a (valid) intermediate CA certificate and can run havok with this one.


What is the difference between a forgery attack and an user impersonation attack?

Forgery and impersonation attacks are different. Forgerty attacks target on verifiability where impersonation attacks target on authentication. However, they are somewhat linked, as detailed below.

In cryptography, many schemes such as digital signature, message authentication code, verifiable secret sharing etc. require verifiability.

In such a scheme, a user has a key pair $(k,vk)$ ($k$ and $vk$ can be the same or different). There is an algorithm $f(m,k)$ that takes a piece of data $m$ and the secret key $k$ as input, and output some cryptographic data $c$, and there is another algorithm $v(m,c,vk)$ that takes data $m$ and $c$, and the verification key $vk$, and outputs 1 if $c$ is indeed generated using $f$ from $m$ and $k$, and outputs 0 otherwise.

Forgery attack in this context means an attacker who has no knowledge of the secret key $k$ can generate a pair $(\bar{c},\bar{m})$ such that he has never seen $f(\bar{m},k)$ before, and $\bar{c}$ can pass the verification, i.e. $v(\bar{m},\bar{c},vk)=1$.

A forgery attack can (but not necessarily) lead to an impersonation attack. An impersonation attack is when an adversary can successfully claim an identity that he doesn't possess, and pass authentication (i.e. he can pretend to be another person in the system). Many authentication protocols rely on verifying some cryptographic data, if the cryptographic data can be forged, then authentication will admit the wrong person.

One prominent example is many authentication protocols rely on PKI, and require the party to be authenticated to provide a valid certificate, and the validation of the certificate relies on much on the CA's signature on the certificate. If one can forge the CA's signature, he can forge a certificate, thus be authenticated as another person.


Hash 22 byte secret into 512 bit hash: Full entropy?

Yes, the 512-bit hash (using Keccak-512 or the like) of 22 bytes (176 bits) entered by a user (or from whatever source) has the full entropy of the input (that is: at most, 176 bits of entropy; much, much less for a user-specified 22-character string) for any practical purpose; and not as much entropy as there are bits in the hash's output. Argument that there is no reduction of the original entropy: odds that among the $2^{176}$ 176-bit strings, any two hash to the same value, are only $\approx 2^{-161}$, making the operation theoretically reversible (including for every input) with overwhelming odds. Arguments that entropy is not increased to the hash's width: the number of possible outcomes is no more than $2^{176}$ 512-bit values, which are fully determined by the specification of the 512-bit hash; and no deterministic process can increase entropy.

In fact the reduction in output entropy compared to input entropy remains mostly negligible for input of 63 bytes (or less); or more generally for input of at most $n-1$ bytes for an $n$-byte hash. Argument: even though the transformation is no longer reversible for every input, it still is expected to be reversible for a large majority of inputs.

This justify Owlstead's suggestion of using a narrower hash, such as SHA-224 or SHA-256, since the output will be smaller but have almost the same entropy.

However it makes only limited sense to hash a user-specified string: since the input is chosen by a user, it is vulnerable to guessing, and replacing that input by its hash won't solve that issue. For this purpose it should be used a key stretching mechanism, such a scrypt (or the more common but much weaker PKBDF2). Key stretching does not increase entropy, but greatly increases the difficulty of brute-force search (about: by the ratio of effort spent for stretching, to the effort necessary to decide is the stretched key is correct; that can be $2^{30}$ in some realistic situations, like a password-protected document).


I'm assuming you are talking about the typical dynamic RSA accumulator from "Dynamic Accumulators and Application to Efficient Revocation of
Anonymous Credentials", by Camenicsh and Lysyanskaya (see PDF here).

First, recall that the accumulator over prime elements $x_1, x_2, \dots, x_n$ is computed in $O(n)$ time as:
\begin{align*}
A &= g^{x_1 x_2 \cdots x_n}
\end{align*}

Second, recall that after removing some $x_i$ from the accumulator $A$, we end up with a new accumulator $A'$:
\begin{align*}
A' &= g^{x_1 x_2 \cdots x_{i-1} x_i \cdots x_n}
\end{align*}

To answer your first question,

  Why is it simpler to calculate the new accumulator value after a deletion if the secret $\phi(N)$ is known?

Because knowing $\phi(N)$ allows us to easily compute $A'$ from $A$ as follows:
\begin{align*}
A' &= A^{{x_i}^{-1} \bmod \phi(N)}
\end{align*}

To understand this, recall that additions and multiplications are reduced modulo $\phi(N)$ "in the exponent."
Also recall that numbers that are coprime with $\phi(N)$ (e.g., $x_i$) have multiplicative inverses $\bmod \phi(N)$ [1].

Note that you can compute $A'$ from $A$ directly, without needing to know the other accumulated elements $x_j, j\ne i$.

To answer your second question,

  Is possible to calculate the deletion only with the RSA modulus $N$?

I'm assuming you mean "calculate the new accumulator." The answer is "yes," and you can probably see why.
Remember that, just like we can compute $A$ in $O(n)$ time, we can also compute $A'$ in $O(n)$ time (i.e., by repeated exponentiations):
\begin{align*}
A' &= ((((((g^{x_1})^{x_2}) \cdots)^{x_{i-1}})^{x_i})\cdots)^{x_n}\\
   &= g^{x_1 x_2 \cdots x_{i-1} x_i \cdots x_n}
\end{align*}

Later edit: As @Maeher nicely pointed out, without the trapdoor you need to know the other elements $x_j, j\ne i$ in order to remove $x_i$, since removing is just recomputing the accumulator without $x_i$.

If you are interested in an accumulator where you can both add and remove without knowing the other elements, you can read the elegant work by Papamanthou et al on "Streaming Authenticated Data Structures" from EUROCRYPT'13 (PDF here). Computing new witnesses requires knowing at least part of the accumulated elements, since the construction is merely a different kind of Merkle tree. However, unlike a Merkle tree, existing witnesses can be updated given just the added/deleted elements (no need for additional sibling paths). Currently, this accumulator is based on lattices and will be less efficient.

Still, Qian et al implemented it in "Streaming Authenticated Data Structures: Abstraction and Implementation" at CCSW'14 (PDF behind paywall).

Hope this helps 2 years later :)


X509 certificates: Two Algorithm Identifiers?

I'm assuming you're talking about these two fields:

signature
signatureAlgorithm

following the names defined in RFC 5280 section 4.1. And section 4.1.1.2 then goes on to state (for signatureAlgorithm):

  This field MUST contain the same algorithm identifier as the signature field in the sequence tbsCertificate (Section 4.1.2.3).

So, yes, they have to be the same.


Why it is said that “zk-SNARKs need a trusted setup” to work?

It is not true that zk-Snarks need a trusted setup. It's just that all the zk-Snarks that depend on pairings (that I know of) hinge on a "trapdoor", the knowledge of which makes the scheme insecure. And before 2019, those were the only known zk-Snarks.
zk-Starks do not rely on pairings. Neither do bulletproofs. Bulletproofs are arguably not Snarks, since the verification time is not succinct.
The DARK scheme gives you a trustless zk-Snark (https://eprint.iacr.org/2019/1229). Recently, a gap was found in this paper but the cryptographers who found the gap were able to modify the scheme so that it is now secure and hinges on weaker cryptographic assumptions than before: https://eprint.iacr.org/2021/358.


Does a reuse of the Mac key reveal information about the key itself ?

One would certainly hope not - Message Authenticate Codes are supposed to be able to be safely used with the same key multiple times.

There is one caveat - the Poly1305 algorithm does need a nonce, which must be different whenever you MAC a message (specifically, you cannot reuse the same (key, nonce) pair to MAC two different messages) - if you do, you do leak enough information for someone to generate a forgery.


What is an advantage of MDS matrices in block ciphers?

They said that, one goal of MDS matrices is to protect the block ciphers against linear and differential attacks.

That would probably depend on the cipher, but in generally, pretty accurate.

  is constructing the bias table of MDS matrices behavior impossible?

Actually, it's trivial; MDS matrices are completely linear, and so they have probability 1 linear and differential trails.

So then, if MDS matrices, in themselves, offer no protections against linear and differential cryptanalysis, why are they said to help greatly?

Well, it's because they help other components within the cipher work a lot more effectively, as it forces any linear/differential characteristic to go through most of the cipher.

Consider this simple design:

     |       |      |      |
   sbox    sbox   sbox   sbox
     |       |      |      |
    ------ MDS Matrix ------
     |       |      |      |
   sbox    sbox   sbox   sbox
     |       |      |      |

Then, for any linear characteristic, that characteristic must go through at least 5 of the sboxes; that's because for any nonzero change, the MDS matrix ensures that the number of input lines changed plus the number of output lines changed is at least 5.  So, if the sbox have a best linear characteristic of $\epsilon$, then the best path here is at most $\epsilon^5$.

If we scale this toy example up into something realistic (e.g. AES), then any path must go through a huge number of sboxes, and so any path is effectively dampened out.


That would work and almost certainly wouldn't have any negative impact on security, but it would be cleaner just to have a string of 16 0x00 bytes at the start of a message, instead. Not only does this save you the trouble of hashing, but you stay within the standard threat model for CBC which assumes the IV is independent of the message blocks. (One can come up with pathological yet technically still secure hash functions that would cause your approach to become insecure.)

And a quick note: the block size is 16 bytes, not 32 bytes. The 256 in AES-256 refers to the length of the key, not the block.

You should look into using a message authentication code, such as HMAC. Doing so will not only validate a correct passphrase, but will also ensure the ciphertext has not been tampered with. (CBC will prevent someone from learning information about the plaintext, but will not stop someone who already knows it from tampering with the ciphertext so that parts of it decrypt to strings of his choosing.)

Edit: A couple warnings, if you decide to go with a MAC (and I think you should): (1) Use different keys for CBC and the MAC; (2) MAC the ciphertext, not the plaintext; (3) Concatenate the IV to the ciphertext before using the MAC.


primitive root of a very big prime number (Elgamal DS)

When considering a big prime $p$, the group of invertible integers modulo $p$ are all integers from $1$ to $p-1$. There are $p-1$ of them. The order of an integer $g$ modulo $p$ is the smallest integer $k > 0$ such that $g^k = 1 \pmod p$. Group theory states that the powers of an element $g$, i.e. $1$, $g$, $g^2$... are collectively a subgroup of the group of invertible integers modulo $p$, and the order of $g$ is really the size of that subgroup (called "the subgroup generated by $g$"). The cardinal of a subgroup is always a divisor of the cardinal of the group that contains it. Thus, $k$ divides $p-1$.

A primitive element $g$ is one such that the subgroup it generates really is all of the invertible integers modulo $p$, not just some of them. Therefore, to verify whether an integer $g$ is primitive or not, all you have to do is check that its order is $p-1$ but not one of the other possible subgroup orders. That is, you check that $g^{k'} \neq 1 \pmod p$ for all $k' < p - 1$ such that $k'$ divides $p-1$.

The problem can be simplified as follows: suppose that there is a $k' < p-1$, such that $k'$ divides $p-1$, and $g^{k'} = 1 \pmod p$. We can consider $\alpha = (p-1)/k'$, which is an integer greater than 1, and thus a product of some prime integers (since every integer can be decomposed as a product of prime factors). Let's call $r$ one of the prime factors of $\alpha$ (i.e. we write $\alpha = r\beta$ for some integer $\beta$). Since $\alpha$ divides $p-1$, so does $r$, and we can compute:
$$ k'' = (p-1)/r = \beta k' $$
Thus:
$$ g^{k''} = (g^{k'})^\beta = 1^\beta = 1 \pmod p $$

In other words, if $g$ is not primitive, then there must be a prime integer $r$ that divides $p-1$ such that $g^{(p-1)/r} = 1 \pmod p$.

This means that in order to test whether a given $g$ is primitive, then it suffices to apply the following test:

  Let $p$ be a prime, and $g$ a non-zero integer modulo $p$. If, for all primes $r$ that divide $p-1$, $g^{(p-1)/r} \neq 1 \pmod p$, then $g$ is primitive, i.e. its order modulo $p$ is exactly $p-1$.

Now comes the actual difficulty: you must somehow know the list of prime factors of $p-1$. This is easy if you generate $p$ "specially", as a so-called "safe prime" (the terminology "safe" here is traditional and does not actually imply that the prime is inherently "safer" than any other, but it makes our problem easier). A "safe prime" is an integer $p$ which is such that both $p$ and $(p-1)/2$ are prime. If you generate your modulus for ElGamal signatures are a "safe prime", then there are only two prime factors of $p-1$: these are $2$, and $(p-1)/2$. The test above now becomes the following:

Get a random non-zero $g$ modulo $p$.
Check that $g^2 \neq 1 \pmod p$. Note that there are only two integers $g$ modulo $p$ such that $g^2 = 1 \pmod p$, and these are $1$ and $p-1$. Thus, it suffices to choose $g$ greater than $1$ and lower than $p-1$ to fulfill that condition.
Check that $g^{(p-1)/2} \neq 1 \pmod p$. If that condition is not met, then you must start over with another $g$. Otherwise, that's it, you have a primitive $g$.

No specific value of $g$ is better than any other with regards to resistance to discrete logarithm, so you might just as well try small values of $g$, that offer a small performance boost; you start with $g = 2$ and simply increment it until you reach a primitive value. Exactly half of the integers from $2$ to $p-2$ are primitives, so you do not have to try many times before reaching such a value.

IMPORTANT: Take care that the test above is for a "safe prime". In the general case, if given a prime $p$ without any knowledge of how it was generated, you would have to factorize $p-1$ into its prime factors, a problem which is, in all generality, quite hard to solve for large integers.

While the ElGamal scheme is nominally defined with a primitive root that generates all invertible integers modulo $p$, it can also be applied to a subgroup, at which point it becomes mostly the same thing as DSA. In DSA, it is customary to generate $p$ as follows:

Let $q$ be a random medium-sized prime (e.g. 256 bits).
Let $p$ be a random large prime (e.g. 2048 bits) such that $q$ divides $p-1$. In practice, this means that random integers $z$ are produced, and, for each, $p$ is computed as $p = qz+1$, until a prime $p$ is obtained.
To make an element $g$ of order exactly $q$, a random integer $m$ modulo $p$ is generated, and we set $g = m^{(p-1)/q} \bmod p$. It is easily shown that $g^q = 1 \pmod p$, which means that the order of $g$ is a divisor of $q$. Since $q$ has been chosen to be prime, the order of $g$ can be either $1$ or $q$. If $g \neq 1$, then its order cannot be $1$. Therefore, $g$ will have order exactly $q$ as long as it is not equal to $1$. Probability of $g$ being equal to $1$ is very very small, but even if that happened, then you would just have to start again with another value $m$.

Summary: to get a primitive element modulo $p$, you get random values and then check whether you obtained a primitive element. Primitive elements are not rare, so this works well in practice. However, to do the check, you have to know the factorization of $p-1$, and that is difficult in the general case. Thus, the usual method is to produce the modulus $p$ with a generation method that also lets you know the factorization of $p-1$, e.g. you make $p$ as a "safe prime". Alternatively, you do not look for a primitive element, but for the generator of a subgroup of known prime size (as is done in DSA).


Why isn't the IND-CCA property inherited when sending redundant ciphertext?

[EDIT: I am assuming a public key system here]

IND-CCA2 summary:

get encryption key.
make decryption queries on chosen ciphertexts.
obtain challenge ciphertext on $m_L$, $m_R$, two equal-length messages chosen by you, the attacker. The challenger is suppsed to randomply pick one, encrypt it and return the ciphertext.
make decryption queries as in 2. except that queries on challenge ciphertext are disallowed.
guess if the challenger encrypted $m_L$ or $m_R$

In IND-CCA2 decryption oracle, Step 4 logic is "decrypt only if the ciphertext is not the same as the challenge ciphertext".

How would you define "same" in the modified case? (Does the decryption oracle require all three pieces to match? If so the new scheme is clearly not IND-CCA2 - the attacker can ask for decryption of a ciphertext where one piece is random). Once "being same" is properly defined, it will be simple to check if the new scheme is IND-CCA2 or not .

By the way, you probably need IND-CCA2 instead of IND-CCA.

Also, you should check out the R-CCA security notion, where Step 4. is replaced by:

make decryption queries as in 2. except that if ciphertext decrypts to one of the challenge messages, the oracle returns "INVALID".

I recall seeing this definition of R-CCA but don't recall where. If you want, I can dig thru the references and post a link.

[EDIT:] One reference for R-CCA is this IACR eprint article, Section 1.3.


In simulation proofs of MPC, why could random oracle extract adversary's input?

This is exactly what makes the random oracle model an idealized model. If $H$ is a hash function in the standard model, an adversary can run $H$ "in its head", and this will be inscrutable to a simulator. But in the random oracle model, the only way to evaluate the hash function $H$ is through a well-defined oracle interface. The simulator gets to play the role of this interface! -- just like it is allowed to play the role of the honest parties.

If SIMs could do that, does it mean we can extract inputs simply by asking the parties to hash their inputs, and any semihonest-secure protocols become malicious-secure ones by simply introducing an extra hash-input step (which is obviously not true) ?

If the protocol instructs parties to hash some information, and that adversary does it, then, yes, the  simulator (in the random oracle model) will be able to observe that call to the hash.
But an adversary can just not call the hash function at all (and just send junk messages in the protocol), or hash the "wrong" value instead, or hash a billion "decoy" values.
The simulator will need to do something sensible in all of these cases!
In your hypothetical example, the protocol would need to contain some method for the other participants to "check" that the hash was called.
I'm not sure what this would look like in your scenario.
But it would have to give the simulator some advantage: after seeing how the adversary acted in the rest of the protocol, along with seeing the list of all random-oracle queries made by the adversary, hopefully the simulator can deduce which query was the "real" one.
I think you will find that the examples in "How to Simulate It" will have this property.
You can't just ask an adversary to query $H$ on their private input, but then do nothing with the result.
They have to interact with $H$ in a way that gives the simulator an advantage, when the simulator is allowed to observe all queries to $H$ and also observe the rest of the protocol messages too.
I'm sure you will see that in "How to Simulate It", the simulator will "cross-reference" these tables $T_1$ and $T_2$ with protocol messages sent by the adversary, in order to extract.


What operations provide perfect secrecy other than modulo addition

Any group operation works for a one-time-pad if you can shoehorn a message uniquely into a group element—addition modulo $n$, multiplication modulo $n$ if you can uniquely encode a message block as an integer coprime with $n$, addition or multiplication in finite extension fields, invertible matrix multiplication over finite fields, whatever group you want—and can be extended by a direct product to arbitrary-length messages: if you have a group operation $m \oplus k$, then you can extend it to an $\ell$-block message $(m_1, m_2, \dotsc, m_\ell)$ with an $\ell$-block key $(k_1, k_2, \dotsc, k_\ell)$ by $(m_1 \oplus k_1, \dotsc, m_\ell \oplus k_\ell)$.  Conventionally we talk about addition modulo 26 in English, or use addition modulo 2 for computers, of course.

Going beyond the one-time pad approach, to encrypt a $t$-bit message, you could choose a permutation $\pi$ uniformly at random from all $2^t!$ possibilities; then the one-time cipher $m \mapsto \pi(m)$ has ‘perfect secrecy’ too.  Of course, it's tremendously inefficient even compared to a one-time pad!  (Bonus: You could get built-in authentication with forgery probability bounded by $2^{-f}$ by using $m \mapsto \pi(m \mathbin\| 0^f)$.  Of course, still much cheaper to compose a one-time pad and one-time authenticator…)


What is meaning of "Decipher the rest of the message by deducing additional words"?

"Deduce" = "guess, and test your guess"

You know where the letters t,h, and e are, so you might find a sequence "the-e". You can guess this will be "there" in the message, and then you have the substitution for r which you can also try, filling in more gaps and giving you essential clues for other words. If anything starts to look wrong, backtrack and revise one of your earlier guesses.

This is a lot like attempting a crossword, but the clues are the context of the words in the message.


Does changing the order of the steps within a round affect the security of AES?

Short answer

Changing the order of the operations does not weaken the security of $\mathop{AES}$ (nor does it increases it).

Long answer

Remark: While ShiftRows and SubBytes are commutative ($f\ g : A \rightarrow A,\ f \circ g = g \circ f$). They are not commutative MixColumns. Therefore changing the order of operations will not produce the same result. But this is not relevant because we are looking from the security point of view.

The order of the operations inside the round function does not matter. This can be shown by observing the propagation of the byte dependence over 2 application of the round function.

In this analysis I'm ignoring the key addition because this operation can be placed anywhere in between all the operations given some tweaking. Thus we can see that the diffusion of a difference is the same as the one in the original specifications. The main reason of this result is due to the strong alignment in Rijndael.

Also this is further explained in Chapter 3 and 5 of The Design of Rijndael by their implementors.


Is the keystream transmitted with the ciphertext when a stream cipher is used?

The keystream is as long as the message, so you don't want to send that to the receiver. The keystream is generated by a much shorter key (e.g., 128-bit private key). That is what the receiver needs in order to decrypt the message.

So, how do you get that to the receiver? Well, clearly you can't just send it in the clear or anyone watching the channel would have the key and could decrypt. Typically what we do in cryptography is run a key establishment protocol. This could be as simple as Alice and Bob meet up and exchange the key on a written piece of paper or as complex as using asymmetric crypto, with public/private key pairs, certification authorities, etc.


No. It is not secure. This is very simple substitution algorithm. It shows patterns clearly. If the encrypted message is long enough or if you have many short encrypted messages, you can crack it using simple frequency analysis. You don't need any complex technique to crack it.
Example:
let data = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
let key = "12345";
console.log(data.encrypt(key));
console.log(data.encrypt(key));
console.log(data.encrypt(key));

Result:
dopqrsopqrsopqrsopqrsopqrso~1}11pqrsopqrsopqrsopqrsopqrsb
dopqrsopqrsopq}33rsopqrsopqrso~3pqrsopqrsopqrsopqrsopqrsq
Nqrsopqrs}38opqrsopqrsopqrsopqrsopqrsopqrsopqrsopqrs~0opv

You see patterns clearly.


A multisignature scheme would be a signature scheme where several parties all sign the same message. So this is not what we are looking for.

What we are looking for is called an aggregate signature scheme. In such a scheme, we have $\ell$ distinct users, each with their own public key $\mathsf{pk}_i$. Each of those users has a distinct message $m_i$ that they would like to sign.
The goal of the aggregate signature scheme is to create a single short signature that convinces any verifier that each user $i$ did indeed sign their respective message $m_i$.

To do so, there in general exist five algorithms:

$\mathsf{KGen}(1^n)$: outputs a keypair $(\mathsf{sk_i},\mathsf{pk_i})$.
$\mathsf{Sign}(\mathsf{sk_i},m_i)$: outputs a signature $\sigma_i$.
$\mathsf{Vfy}(\mathsf{pk_i},m_i,\sigma_i)$: outputs $1$ if the signature is valid and $0$ otherwise.
$\mathsf{Agg}((\mathsf{pk_1},\dots,\mathsf{pk_\ell}),(m_1,\dots,m_\ell),(\sigma_1,\dots,\sigma_\ell))$: outputs an aggregate signature $\sigma$.
$\mathsf{AggVfy}((\mathsf{pk_1},\dots,\mathsf{pk_\ell}),(m_1,\dots,m_\ell),\sigma)$: outputs $1$ if the aggregate signature is valid for all messages and $0$ otherwise.

Standard Correctness applies, i.e. for all messages $m_i$ and all key pairs $(\mathsf{sk}_i,\mathsf{pk}_i) \gets \mathsf{KGen}(1^n)$ it holds that
$$\mathsf{Vfy}(\mathsf{pk_i},m_i,\mathsf{Sign}(\mathsf{sk_i},m_i)) = 1$$
and
$$\mathsf{AggVfy}\left((\mathsf{pk_1},\dots,\mathsf{pk_\ell}),(m_1,\dots,m_\ell),\mathsf{Agg}\left(\begin{array}{c}(\mathsf{pk_1},\dots,\mathsf{pk_\ell}),(m_1,\dots,m_\ell),\\(\mathsf{Sign}(\mathsf{sk_1},m_1),\dots,\mathsf{Sign}(\mathsf{sk_\ell},m_\ell)\end{array}\right)\right) = 1$$

In addition to standard unforgeability we also require unforgeability of aggregated signatures. I.e. we require that for all polynomial time adversaries $\mathcal{A}$ there exists a negligible function $\epsilon(n)$ such that
$$\Pr_{(\mathsf{sk}_1,\mathsf{pk}_1) \gets \mathsf{KGen}(1^n)}\left[\mathsf{AggVfy}\left(\begin{array}{c}(\mathsf{pk_1},\dots,\mathsf{pk_\ell}),\\(m_1,\dots,m_\ell),\sigma\end{array}\right)
 :\left(\begin{array}{c}\mathsf{pk}_2,\dots,\mathsf{pk}_\ell,\\m_1,\dotsm_\ell,\sigma\end{array}\right)\gets\mathcal{A}^{\mathsf{Sign}(\mathsf{sk}_1,\cdot)}(\mathsf{pk}_1)\right] \leq \epsilon(n)$$

The first instantiation of such a signature scheme is due to Boneh, Gentry, Lynn, and Shacham in their paper Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. (See specifically Section 3.1.) In their scheme an arbitrary number of signatures can be aggregated in an aggregate signature that consists only of a single group element.

There are many other instantiations of this primitive from different assumptions and with special properties such as the ability to do sequential aggregation.

While some of those schemes have probably been implemented at least benchmarking purposes, I'm not aware of any crypto library implementing aggregate signatures.


Ciphertext compression (Ring-LWE encryption and authentication system) after encryption?

It does indeed mean to compress the ciphertext.

In very simplified terms:

You can think of the ciphertext generated by a Ring-LWE scheme as a bunch of numbers modulo a number $p$, in this case the prime 12289. Indeed, this output is effectively indistinguishable from uniformly random for someone who doesn't know the private key, as per the worst-case hardness theorem for Ring-LWE.

Decryption involves manipulating these numbers using the private key, resulting in a bunch of other numbers modulo $p$. Then, it tests whether these numbers are closer to 0, or 12289. How far away these numbers are from either 0 or 12289 is the error. The error is introduced by the encryption process itself, and is essential to the security of the system. Obviously, if the error is bigger than 12289/2, decryption won't be correct! Parameters are chosen such that the probability that this happens is exceedingly small.

Now, the way that this compression works is by compressing the numbers modulo 12289 all the way down to modulo 256. So if (approximately) $x \in [0, 48)$, then we map: $x \mapsto 0$. If $x \in [48,96)$, we map: $x \mapsto 1$, etc.

Obviously, we lose information, and we introduce a bit more error. Due to the nature of the decryption process, this error is magnified further, quite significantly so. But if the error was small enough to begin with, we can get away with the compression, and we can utilize all the benefits of 8 bit modular arithmetic, which is huge on hardware like AVR.


Should the most significant byte of a cryptograhic key be nonzero?

Many keys do not consist of a single value. Other key types, such as most symmetric keys, don't have a most significant bit or byte as the key value isn't interpreted as an integer. So this question would be different for each key type and encoding.

In general though you would just decrease the "entropy" or key size. This is certainly the case for ECC, and probably most other schemes that use groups theory / modular arithmetic. So yes, that's certainly counterproductive.

Note that if you view the key value as a number that you would only have to set the MSB bit to 1 to ensure that the key value is at least $2^{(n-1)}$ - assuming that the key uses unsigned values of course.

Cryptosystems should define how keys are created. You'd better make sure you keep to the rules of the cryptosystem or security may well go down the drain.


The article is oversimplifying matters. In a real-world scenario, either…

The recipient already has a copy of the public key, or can retrieve a copy from a trusted source. Either way, they can confirm the key is correct by comparing it with the "known good" copy they already have. (This is roughly how PGP works.) Or…
The key has a signature attached to it, signed by a trusted central authority. (This is roughly how SSL/TLS works.)

Either way, your analysis is entirely correct -- attaching a signature and public key to a message doesn't confirm anything on its own.


EdDSA Verification vs. Cofactorless Verification

1. It means that someone possessing the private key $s$ can create signatures which pass verification but not cofactorless verification with respect to the public key $A$.

3. For example, if $C\in E$ is a point of even order (e.g. $2^c$), and the signer replaces $R:=rB$ in step 2 of the signing procedure by $R:=rB+C$, then
$$
  2^cR+2^cH(\underline R,\underline A,M)A
  \;=\; 2^cSB+2^cC
  \;=\; 2^cSB
$$
but
$$
  R+H(\underline R,\underline A,M)A
  \;=\; SB+C
  \;\neq\; SB
  \text.
$$
The private key is necessary to create such a signature because anyone modifying $R$ (or one of the other parameters) after the signature has been finalized (e.g., someone who does not know the private key) is very likely to be caught by $H(\underline R,\underline A,M)$ contributing to the verification formula. (Note this contradicts Cryptostasis' comment above.)

2. Due to the Pohlig-Hellman algorithm, the security of the whole system is dependent on the large prime-order subgroup $E[\ell]$ of $E$, while small prime factors of the group order do not reasonably contribute to the hardness of computing discrete logarithms.
Group-theoretically, multiplication by $2^c$ realizes a projection to the subgroup of $E$ of size $\ell$, which is a direct factor: From the structure theorem of finite abelian groups,
$$ E\;\cong\;E[\ell]\times G\text, $$
where $G$ is an abelian group of order $2^c$, hence multiplication by $2^c$ maps an element to $E[\ell]\times\{e\}\leq E[\ell]\times G$. (And since $\ell$ is coprime to $2$, multiplication by $2^c$ is an automorphism on $E[\ell]\times\{e\}$.)
Thus multiplication by $2^c$ throws away a little bit of information from the factor group $G$, but that wasn't useful anyway.

In practice, it is not going to matter which variant you use. As explained above, cofactorless verification is a little stricter, hence you might run into interoperability problems with non-conforming signers (but I see no reason why anyone would implement it in a way that makes this happen). On the other hand, verification (with multiplication by $2^c$) will take a few cycles more.


How do I create a short signature? (e.g. less than 100 bytes)

The usual recommendation is ECDSA, or if you need a really short signature, BLS.  See “Security.SE: What asymetric scheme provides the shortest signature, while being secure?”, “Security.SE: How to encrypt a short string to a short ciphertext using an asymmetric encryption?”, and “Crypto.SE: Short length asymmetric encryption?” for details.

ECDSA should give you a 320-bit signature with approximately 80-bit security.  BLS can get this down to about 160 bits for the signature.  In other words, with ECDSA, you're down to about 40 bytes for the signature; BLS gets you down to 20 bytes.

If even that is not short enough, there are other schemes in the research literature that purport to offer even shorter signatures (e.g., SFLASH, Quartz), though I've heard some cryptographers express doubts about their security, so using them would be really pushing it, bleeding-edge stuff that might get broken.


In order to answer this question, you first really need to define what a worst-case OWF is. In particular, is it possible to efficiently sample a hard instance? I assume not, because this would be very hard to formalize and I'm not sure it makes sense. If not, then there is an easy answer:

If there exists a weak OWF then $P \neq NP$
If $P \neq NP$ then let $L\in NP\setminus P$ and let $R_L$ be its associated polynomial-time verifiable relation (i.e., $(x,y)\in R_L$ if and only if $x\in L$).
By the definition of a "worst-case" OWF, take a machine that samples $(x,y)\in R_L$ and outputs $x$.
The function would be defined to be $f(y)=x$.


What's your motivation for slow-hashing on the client-side?

It may well be slower than if performed server side (if you're referring to a browser-based application, and the hashing is done with javascript, then it will certainly be slower, even more so if it's a mobile device)
it doesn't provide any extra security, the credential(s) (password, hash of the password, salt derived from password which will be used for hashing the password, whatever...) will still need to be transmitted to the server - there's no way to avoid that

Keep it simple - you're much less likely to introduce some sort of vulnerability into your system.  The following protocol is pretty standard:

send the client's username/password to the server over TLS/SSL (it's worth the effort, really)
slow-hash the client's password with either Scrypt (preferable), or PBKDF2-SHA256 (at least 100'000 iterations) and a user-specific salt (stored in the DB with the hash)
for each login attempt, compare the output of the above with the hash you have stored in the DB

Note: Bcrypt is fine, some people fetishize it, others prefer PBKDF2 because it's more 'standard' (and it's output length is configurable).  Scrypt is the state-of-the-art, although it's less widely used, and can be more complicated to implement.

EDIT

After further consideration, and better understanding exactly what you're asking (I think), I'm going to say yes: what you're proposing is fine, provided certain conditions are met.  The issue that @StephenTouset pointed out is valid, and has to be avoided.  However, if I understand your question correctly, then you're already mitigating that weakness.  Consider the following:

Client slow-hashes password with PBKDF2 or Scrypt (use of email address or username as salt is questionable - email addresses change and usernames could be used in dictionary attacks).  This initial slow-hashing mitigates dictionary attacks, and offloads the heavy work from the server to the client
Client submits the output of the slow-hash (256 bits) to the server (over TLS/SSL), where it is then hashed once with SHA-256 (no salt necessary) and compared with the hash stored in the database.

Should the database be compromised, an attacker would still need to brute-force the hash of a 256-bit value (the client-side slow-hash output) to verify a correct guess at the password, pretty much rendering the hashes stored in the database useless to an attacker.

I think the theory is fine.  In practise, I think it's a bit messy and maybe unwarranted (your comment mentioned up to 1000 login attempts per second, are you really anticipating up to 86 million logins per day??).  Only you can decide whether you can justify it.


Yes, it is related. Claude Shannon in his famous article A Mathematical Theory of Cryptography defines the Confusion and Diffusion. Wikipedia's Confusion and diffusion page  defines diffusion as;

  Diffusion means that if we change a single bit of the plaintext, then (statistically) half of the bits in the ciphertext should change, and similarly, if we change one bit of the ciphertext, then approximately one half of the plaintext bits should change. Since a bit can have only two states, when they are all re-evaluated and changed from one seemingly random position to another, half of the bits will have changed state.

A diffusion matrix transforms columns and it similar to the MixColumns  operation of AES. It is optionally followed by a ShiftRows (like in AES) to provide further mixing where ShiftRows permutes the rows*.

If there is no diffusion matrix applied to AES ( or similar SPN based block cipher, and also no ShiftRows), then only a single bit change in the input will only affect the corresponding byte. Therefore, diffusion is necessary but not sufficient.

* FOAM: Searching for Hardware-Optimal SPN Structures and
Components with a Fair Comparison


Does threshold crypto (m-of-n) guarantee that m peers discover the plain text?

The terminology for what you are describing is called fairness. This comes up often in threshold cryptography. Just knowing the right terminology should help you find many papers on the topic.

In general, fairness is impossible unless there is an honest majority [Cleve1986], though some non-trivial functions can be computed [Gordon2008a, Gordon2008b].

You appear to be most interested in fair threshold decryption of a ciphertext.

The paper Fair threshold decryption with semi-trusted third
parties provides a construction that assumes semi-trusted third parties are available to help. Section 1.1 of that paper, provides a good intro to the related work and some of the different assumptions or paradigms that have been used.


Here is what should be done:

After getting the blinded message M' You should convert it back to string format. (First to hex, then string)
You should convert this m' to base64 like you did.
Send this base64 encoded message to client like you did.

The rest of the solution looks okay.

P.S: There is still a defect in that solution that i can not find.