How to use AES-CBC to password-encrypt a small block of stored data I have a small block of data (16 bytes) that I am required to encrypt,
store (in an unsecure, visible location).  Later I have to retrieve
and decrypt it.  I must use AES-CBC and a user-entered password.

After decrypting the data, I need to know if the correct password was
used (so I can reject the data if not).

My initial plan:

Encapsulate the 16-byte payload in a plaintext frame something like this:

     Frame:
        8-byte random salt
       16-byte data block
        8-byte checksum of salt+payload

Generate a random 128-bit IV.
Generate a 128 or 256 bit key from the user-entered password.
Encrypt the plaintext frame using IV+key.
Concatenate the IV and ciphertext frame and store them.  [Using 48
bytes of storage.]

Storage size isn't critical: a hundred bytes (or two) is OK, but
thousands is probably too much.

My questions:

Do I really need a random IV if I salt the data?  Prepending
128-bits of random salt to the data is the same as using a 128-bit
random IV, right?
What should I use for a PBKDF?  The application is running on a
smallish, slowish embedded system and has rather limited crypto
routines available (aes, arc4, des3, sha1, sha256, md2, md5).  So,
I'll have to roll my own PBKDF.  A PBKDF algorithm that runs in one
second on an attacker's machine will probably take thousands of
seconds on this device -- so let's not get carried away: I need to
do the encryption and decrypting in no more than a second or so.
Most discussions of using a PBKDF emphasize the importance of
including a salt value.  That means I also have to store the PBKDF
salt along with the IV and the ciphertext, right?
I have access to the stored data produced by a previous version of
this product (which I'm told uses AES-CBC to do the same thing),
but I have no access to source code or the people responsible.  The stored
data is exactly 16-bytes long.  AES-CBC always uses 16-byte blocks,
so that must be a single block of ciphertext.  That means

a) They aren't using any salt in the PBKDF algorithm?

b) They must be using an IV produced by the PBKDF (or a constant
    IV)?

Do I really need a random IV if I salt the data? Prepending 128-bits
  of random salt to the data is the same as using a 128-bit random IV,
  right?

Yes, it should do the job, but if I'm reading your question correctly you don't really have to optimize storage away, but if you want to, I'd rather recommend going with AES-128 and a 128-bit IV which is derived from the PBKDF result (simply split the 256 bits in half).

  What should I use for a PBKDF?

This is a difficult question. If possible you should pick a password hashing function from the password-hashing competition winner's portfolio.
If it's not possible you should implement PBKDF2 with SHA-256, because you then get those 256-bits from a single iteration chain which you can use for key and IV. All you can do optimize your defense is to measure the time it takes for your actual encryption code to run and then give what is left to the PBKDF.

  Most discussions of using a PBKDF emphasize the importance of
  including a salt value. That means I also have to store the PBKDF salt
  along with the IV and the ciphertext, right?

Yes, but as discussed above, you can swap the IV for the salt and derive the IV from the PBKDF output to save space again.

  They aren't using any salt in the PBKDF algorithm?

If they didn't prepend a salt to the ciphertext and the payload is always 16-bytes, then yes, there's no way they're using a salt.

  They must be using an IV produced by the PBKDF (or a constant IV)?

Again, if you don't see an IV, that means that any of the two options holds with the constant one being significantly worse than the PBKDF derived one.

Now that I have actually answered the question, I'd like to point out improvements in your format.

The format:

      16-byte salt
frame:
      16-byte payload
frame-end
      32-byte authentication tag

This way you get a strong salt, which won't yield any collisions and other undesirable outcomes on accident. You can feed it into the PBKDF and get the key and IV (both 128-bit) back for AES-CBC. You use this to encrypt the payload and the payload only. Finally you HMAC-SHA256 the salt, the (temporarily buffered) IV and the payload-ciphertext with the AES-key (yes it's ugly but should be safe) and append this tag to the ciphertext.

This has the advantage, that you don't do hash-then-encrypt which is a worse variant of mac-then-encrypt, you can actually use your salt where it's useful (why was it part of the plaintext in the first place?) and you get strong authentication with overall 128-bit security.


Is HMAC-MD5 collision-resistant if the key is unknown? I'm in a situation where I need to use HMAC-MD5 (for a learning, non-production application) and it needs to be collision-resistant.

So my question: Is HMAC-MD5 collision-resistant if the key is unknown, ie you are only given standard oracle access to an HMAC-MD5 oracle?

Alternatively, if possible you can replace "MD5" with "any Merkle-Damgård hash function for which collisions are known" (which is a more general statement).

Note that "Is HMAC-MD5 still secure for commitment or other common uses?", while related, only talks about the situation with a known key to the adversary.

Yes, HMAC-MD5 with the key secret is still considered practically secure against all attacks, including collisions. We are about in the situation considered in Mihir Bellare's New Proofs for NMAC and HMAC: Security without Collision-Resistance (extended abstract in proceedings of Crytpto 2006).

But as the saying attributed to the NSA goes: attacks only get better; they never get worse.


What's wrong with my security model - or how can it be attacked? I'm working on a little personal project where security is very important, and I've thought for a while about the best way to do this. Now I am looking for a little outside help on good practices. The goal is to store personal text data on a server (like wifi passwords, etc) and be obtained through a password. I wanted to make user accounts for a few friends so that we each could securely store text snippets and retrieve them without the others knowing them. Here's my data structures:

// Account
- Username
- Password
- Salt

// StoredData
- Title
- Info
- User

Okay, now the fun part. Here's how I'm obfuscating the data. When a friend creates an account, their username is salted with a salt in the server config files (this is Rails btw, so ENV['SALT']) and then SHA256'd. The password is generated via BCrypt. The only thing I'm not sure about are how many rounds to do for BCrypt so the server stays snappy; right now it's at default for ruby's bcrypt library. A random salt is also saved in the Account for the next step.

Username = SHA256(username + SERVER_SALT)
Password = BCrypt(password)
Salt = BCrypt.generateSalt

When a friend saves their data, it is encrypted using AES-256. So for this, an AES Key is generated using a combination of their plaintext username and password, as well as the salt generated in Account creation. That key is never stored on the server, but created on device at runtime.

         PBKDF2_HMAC_SHA1(secret, salt, rounds)
AESKey = PBKDF2_HMAC_SHA1((usernamepassword), Account.Salt, 20000)
Title = AES-256(AESKey, title)
Info = AES-256(AESKey, info)

Last but not least, every time you login, you are given a SessionKey that enables you to perform any function like editing or creating new data. This SessionKey rolls after every action. So, on login you get S1, then you make a new piece of data and S1 is deleted and S2 is given to you. So on and so forth. Each SessionKey has a one hour time limit as well. Here's my data structure for that:

// SessionKey
- Key (32-bit GUID)
- HashedUser
- ExpirationDate

Also, the whole thing is sent back and forth over SSL, though after the recent revelations I'm not too sure how secure that is anymore. My question to the community is - what am I doing wrong? No crypto implementation is being rolled by me, I'm just using multiple stock implementations. BCrypt is 10 rounds and PBKDF2 is 20,000 right now. Are those high enough for contemporary cryptography and the computer systems I know some people have? Are there any gaping holes? Is the whole thing wishful thinking?

Usernames

A hashed username is fine; a nice idea for the security paranoid actually. If all username records use the same salt, then a rainbow attack is theoretically possible - as is knowing that a user has X pieces of secured information (plus timestamps etc). But you need a single salt per table if the username is the tuple selection mechanism.

Secret Snippet (Title/Info/Visible Timestamps)

Depending on other features this service is providing, the password needn't be stored server-side to secure the secret snippets; thus avoiding the time cost of bcrypt. If user enters the wrong password your service can happily decrypt and return semantic garbage. If the user enters an unmatched username the server can happily invent a random editable list of random data; breaking any clue about viable usernames. Context-specific flags or checksum verification could be used by the client agent to discard deciphered garbage.

Storing a password on a server is usually used for authentication instead of  confidentiality. Whether a computer should do something for someone - instead whether the data returned is fit-for-purpose. The users can simply be told to pick an unguessable username if they don't want their data erased or modified; in a manner similar to disposable email inboxes. If the username is guessed, the content is still unintelligable.

Session Key

Seems legit. If session doesn't include the decryption password or aggregate AES key and user wants to see the plaintext content, the user's client-side will need to cache the password or plaintext; or the persistent session will still bug the user for a password on each page refresh.

Other Thoughts

Alternately, if the service simply stores secure information; then an ad-hoc public key approach can be used with decryption occurring on the client-side. And yes, to those naysayers, you can have unverified use of public keys; if a service is indifferent to whether the human using the username has changed or simply their password. A SSL framework provides the protection against man-in-middle attacks. If it doesn't - you have to reinvent a much larger wheel.


Compressing BLS signature with a hash function It seems to me, that it should be possible to hash BLS signature to achieve significant space saving. Here is how it could work:

Assuming we have a pairing-friendly elliptic curve with two generator points $G_1$ and $G_2$. Let's say my public key is $P = p \cdot G_1$, where $p$ is my private key. The standard BLS signature of message $m$ would be:

$$
S = p \cdot H(m)
$$

where, $H$ is a hash function that maps the message into the subgroup defined by $G_2$. The verification of the signature is done using a pairing function $e$ as follows:

$$
e(P, H(m)) \stackrel{?}{=} e(G_1, S)
$$

If we use a curve such as BLS12-381, the size of the signature could be 96 bytes. But what if we redefine the signature as:

$$
s = H_2(e(G_1, p \cdot H(m)))
$$

where, $H_2$ is a cryptographic hash function (e.g. SHA256). The verification can then be done as follows:

$$
H_2(e(P, H(m))) \stackrel{?}{=} s
$$

Not only is the signature now only 32 bytes, but it also takes only 1 pairing to verify.

The obvious drawback is that signatures can no longer be aggregated, but I'm wondering if there are any other issues with using this scheme.

but I'm wondering if there are any other issues with using this scheme:

  $H_2(e(P, H(m))) \stackrel{?}{=} s$

The obvious problem is that anyone with the public key can compute everything on the left side, and hence forge a signature to any message they want.


Understanding Diffie-Hellman Key Exchange Help me understand the Diffie-Hellman Key Exchange

From what I understand:

Agreed upon numbers: Both parties agree on the value of a large prime number $p$ and a generator $g$.
The users each choose private keys; Alice chooses $a$ and Bob chooses $b$, such that $0<a,b<n$.
The users each calculate public keys: Alice computes $A=g^a\pmod{p}$, while Bob computes $B=g^b\pmod{p}$. Each sends the other their public key.
The users calculate the secret key $k$ as the other person's public key raised to the power of their own private key mod $p$. Alice calculates it as $B^a\pmod{p}$, Bob as $A^b\pmod{p}$.

Example: $p=7, g=4$. Alice chooses $a=2$, Bob chooses $b=3$, Charlie chooses $c=4$. Then the public keys are $A=4^2=16$, and $B=4^3=64$, and $C=4^4=256$.

In that case, Alice and Bob will compute $$k_{ab}=64^2=16^3=4096\equiv1\pmod{7}$$

Alice and Charlie will compute
$$k_{ac}=256^2=16^4=65536\equiv2\pmod{7}$$

Questions:

Why does $p$ need to be a prime number?
How does the size of $p$ affect its security?
What's a generator ($g$)?
Why must the private key be less than $p$?
What is mod?
what maths/types of logic formulate the science behind this kind of cryptology?

Also, please correct me if I've made any errors above. Please feel free to offer any additional information that you think will aid in understanding this concept.

$p$ must be a prime number to construct a cyclic group with $p-1$ valid private exponents. Using a composite number might impose security issues and possibly performance penalties.
The size of $p$ dictates the security as it forms the size of the field. The larger the field, the more private exponents to try. The more effort you have to find the used one.
A generator is a group element that has order $\phi(p)=p-1$, so the following equation must hold for a generator $g^t\equiv 1 $ $(mod$ $p)$ where $t$ is the least interger such that this equation holds. This least integer must be $p-1$. Also look at this question to understand why a generator is required.
It would be pointless to choose a private exponent larger than $p$ as one would be again at the bare generator for $g^p\equiv g$ and hence one can save these cycles.
$"mod"$ is the binary operation that outputs the remainder of integer division. For example$7$ $mod$ $3 = 1$ as $7=2*3+1$, mathematicans also write $7\equiv 1 (mod$ $3)$.
This is called "asymmetric cryptography" and number theory is usually the tool used by cryptographers to construct such schemes.

For further understanding, reading one of the established books does help. (like the Handbook of Applied Cryptography as proposed in the comments)


Is there a standardized tree hash? SHA-1, SHA-2, and the standardized version of SHA-3 are all sequential.  This is impractical for hashing very large files distributed across machines.  Any sequential hash can be straightforwardly converted into an efficiently parallelized hash using Merkle trees, but then I lose the standardization, and this is undesirable if the hash is to be used for long term authenticated storage.

Question: Is there an officially standardized tree-based (parallelizable) hash?

The most important property of the tree-based hash for my purposes is that for any partition of the input string, each portion can be reduced down to $O(\log n)$ intermediate space in parallel such that the intermediate values can be combined into the final hash, with at most a constant factor overhead over a sequential hash.

With SHA-3 Derived Functions (SP 800-185, pdf) there is now a standardized parallel hash based on SHA-3, called ParallelHash, appropriately.

However, it is not a tree hash, but more of a hash-list-based mode. The string to be hashed is divided into equal-sized blocks, which are hashed, concatenated and then hashed again.

While it is not a tree hash it should cover the use case of hashing very large files across many machines. The arbitrarily small blocking size allows you to get to your $O(\log n)$ requirement if you base it on an appropriate function of the input size.


using hash function of (key||plaintext) instead of random value for IV for a protocol which implements AES under CBC mode, an $IV $(initialization vector) is required for each encryption.
Instead of picking the $IV$ randomly, is it advisable for us to set the $IV$ to be $\text{SHA1}(k||m)$ where
$k$ is the key, and $m$ is the $1^{st}$ 128 bits of the plaintext, e.g is this scheme semantically secure?
Any thoughts is welcome! Thanks!

No, it's not semantically secure.

Proof: select two plaintexts with identical initial 128 bits; and present them to the Oracle to be encrypted.  The resulting ciphertexts will also have identical initial 128 bits, hence the encryptor can be distinguished from something that generates random outputs.


ElGamal Homomorphic Encryption Formula Question With Public Key $(G, q, g, h)$ where $G$ is a group, $q$ prime, $g$ a generator of $G$, Am I right in thinking that:
$$\mathrm{Enc}(m;r) := (g^r, h^r \cdot g^m)$$

TL;DR: as pointed by DrLecter in comment¹, the question's formula is for exponential ElGamal encryption, with per-encryption random $r$ explicit.

I'll first describe (straight) ElGamal encryption. It works in an arbitrary finite cyclic group of generator $g$ and order $q$ (with the internal law noted multiplicatively). That is, $q$ is the smallest strictly positive integer with $g^q=1$, where $1$ is the neutral in the group (the integer $1$ when working in a subgroup of $\Bbb Z_p^*$, or the point at infinity for an Elliptic Curve group). Private key is an integer $x$ in $[0,q)$. Public key can² be $h=g^{q-x}$.

Encryption of a message supposes that it was mapped to an element $\widetilde m$ in the group by some encoding technique. Encryption draws a random integer $r$ in $[0,q)$, and outputs the ciphertext consisting of two group elements per the formula (different from that in the question):
$$\mathrm{Enc}(\widetilde m,r)\gets(g^r,h^r\cdot\widetilde m)$$

(Straight) ElGamal decryption of ciphertext $(c_1,c_2)$ produced as above obtains $\widetilde m$ as follows:
$$\begin{align}
\mathrm{Dec}(c_1,c_2)&\gets {c_1}^x\cdot c_2\\
&\;={\left(g^r\right)}^x\cdot h^r\cdot\widetilde m\\
&\;=(g^r)^x\cdot (g^{q-x})^r \cdot\widetilde m\\
&\;=g^{rx+(q-x)r}\cdot\widetilde m\\
&\;=g^{qr}\cdot\widetilde m\\
&\;=(g^q)^r\cdot\widetilde m\\
&\;=1^r\cdot\widetilde m\\
&\;=\widetilde m\\
\end{align}$$
(Straight) ElGamal encryption is multiplicatively homomorphic (for multiplication of plaintext as mapped in the group), per the easily established relation
$$\mathrm{Enc}(\widetilde m,r)=(c_1,c_2)\quad\mathrm{Enc}(\widetilde m',r')=(c'_1,c'_2)\implies\mathrm{Dec}(c_1\cdot c'_1,c_2\cdot c'_2)=\widetilde m\cdot\widetilde m'$$
There are functional issues with (straight) ElGamal encryption:

It is non-trivial to map and unmap an applicative message $m$ to and from an element $\widetilde m$ of the group. In $\Bbb Z_p^*$ with $q$ prime or in an ECC group, practical methods are iterative. When working in $\Bbb Z_p^*$ with $p$ prime and $q=p-1$ (implying $q$ is not prime for sizable $p$), we can take $\widetilde m=m$ but then ElGamal encryption leaks one bit³ of information about $m$.
Multiplicative homomorphism is less useful than additive homomorphism, and not directly useful since the multiplication is on mapped messages $\widetilde m$, rather than on arbitrary messages.

Here exponential ElGamal encryption comes to the rescue, solving both problems, at the expense of making decryption hard. Its encryption takes plaintext $m$ in $\Bbb Z_q$, maps it to $\widetilde m=g^m$, then encrypts per straight ElGamal. The encryption formula becomes as in the question:
$$\mathrm{Enc}(m,r)\gets(g^r,h^r\cdot g^m)$$
Exponential ElGamal decryption decrypts per straight ElGamal yielding $\widetilde m$, then either verifies an externally supplied guess $w$ of the plaintext by checking if it holds $g^w=\widetilde m$, or solves that discrete logarithm problem yielding $w=m$.

Exponential ElGamal encryption is additively homomorphic (for addition of plaintexts modulo $q$) by composing ciphertexts as in straight ElGamal encryption.

Note: while getting $m$ in exponential ElGamal decryption requires solving a discrete logarithm problem, that's still possible for moderately large $m$, including deterministically by using baby step/giant step, which has cost $\mathcal O(\sqrt m)$ group operations. Also, when in a sugroup of $\Bbb Z_p^*$, sizable speedups are possible because the discrete logarithm for base $2$ is easier: we use $g=2$, or modify encryption to $\mathrm{Enc}(m,r)\gets(g^r\bmod p,h^r\cdot2^m\bmod p)$ with $2$ of the same (prime) order $q$ as $g$.

¹ That was minutes after the question was posed and years before this answer.

² Sometime the public key is given as $h=g^{-x}$, which is equivalent, or as $h=g^x$, in which case $x$ should be changed to $q-x$ or equivalently $-x$ for decryption.

³ The Legendre symbol $\bigl(\frac mp\bigr)$ can be found from the ciphertext. This issue was not highlighted in the original description: Taher ElGamal's A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (July 1985 in IEEE Transactions on Information Theory, formerly in proceedings of Crypto 1984).


DES security if used a SHA3 function instead of Normal DES function? I was practicing some python programming and I decided to implement a simple DES encryption function, so i decided to take some shortcuts so instead of DES expansion boxes and s-Boxes i just used a simple keyed SHA3 hash function the input is: 32-bit right side + key(any length I want but I used 128-bit) The first 32-bit of hash are xor-ed with left side to produce ciphertext. So now ignoring that i designed my own crypto and the fact that I used a very simple key schedule function. what are the security advantages of using this hash function instead of normal one (taking in mind that it takes 128-bit key which is greater than 56-bit key of Normal DES), and how it will differ if I used SHA2 (would SHA2 susceptibility to length extension attacks affect the security). lastly what are the advantages of using this method.

The question as initially asked essentially considers a 64-bit symmetric Feistel cipher with 16 rounds, a large (128-bit) key, a near-ideal round function, but the same function and key at each round. A slide attack allows at least a distinguisher, I think with in the order of $2^{31}$ queries to an encryption oracle. With some more, it might be possible to construct plaintext/ciphertext pairs that where not queried. This is an interesting exercise. That makes the security lower than that of DES from several standpoints.
If there is a good key schedule (e.g. if the round counter is appended to the input of the hash), then we are back to a Feistel network, which given the block size and ample rounds is extremely secure. I very much doubt there's an attack better than brute force of the 128-bit key. Security is way above that of DES (but performance in native code is much lower).
With a key schedule based on rotation as in comment, things depend on the rotation count. But if it's by an odd number of bits, nothing disastrous will happen for overwhelmingly most key values.
If there was a security difference between SHA-2 and SHA-3, that would imply a break of one of these (against a random oracle model for constant input length). On top of that it would be with the attacked hash embedded in a setup extremely hostile to attacks. I discount that.


Why are LMS and XMSS not candidates in the Post-Quantum Cryptography Standardization process? Why are Leighton-Micali Signature Scheme (LMS) and eXtended Merkle Signature Scheme (XMSS) not candidates in the NIST Post-Quantum Cryptography Standardization process?
Both are mentioned in the final draft of Recommendation for Stateful Hash-Based Signature Schemes.
I was expecting that both algorithms are candidates in the standardization process as well, but it seems that they weren't even submitted. Can anyone explain why? If they are not considered as candidates for a new standard why does the Recommendation for Stateful Hash-Based Signature Schemes exist and mention exactly those two algorithms?
Is the recommendation just a temporary standard until the standardization process is finished?

Can anyone explain why?

That is because NIST specifically stated that stateful schemes were not allowed in the NIST postquantum competition, because they could not be implemented using the API that NIST has defined (which does not allow any state).
That would appear to be reasonable, as stateful hash based signature methods do need extra care to implement safely; NIST 800-208 outlines what NIST believes are reasonable precautions - those precautions are not needed for other algorithms, and hence NIST kept those separate.


Viability of using One-Time-Pad + HMAC in low-volume IoT communications In the Internet-of-Things world there are certain applications that produce very low volume communications. For example reading a water meter once every hour comes to mind. If the reading could be encoded as a 32 bit unsigned integer and adding a 24 bit serial number this device would transmit only about 614 KBytes of data over an assumed life-time of 10 years (7 bytes * 24 hours * 365 days * 10 years).

I'd like to put for discussion whether a One-Time-Pad (OTP) solution plus HMAC could be a viable solution in this scenario. A key stream of 614 KBytes could be easily pre-generated and stored on the device, although a Hardware Security Module (HSM) implementing "OTP + HMAC" probably does not yet exist.

I am aware of the core problems of using One-Time-Pads in practice. Assuming that these challenges could be overcome (at least in a manner that is sufficiently secure for the purpose of transmitting water meter readings once every hour) the following pseudo-code explains the approach.

# KEYSTREAM is a file containing at least 614 KBytes of random bytes.
# COUNTER is the current offset into KEYSTREAM.
function encrypt_and_hmac(plaintext):
    fp = open(KEYSTREAM)
    fp.seek(COUNTER)

    # Remember the current offset into the KEYSTREAM
    pos = fp.pos()

    # Read bytes from KEYSTREAM for encrypting the plaintext
    cipherpad = fp.read(len(plaintext))
    ciphertext = plaintext XOR cipherpad

    # Read 8 bytes (in this example) from KEYSTREAM for HMAC
    macpad = fp.read(8)
    hmac = hash(ciphertext + macpad)

    # Safely(!) erase the used bytes from the KEYSTRAM
    erase(KEYSTREAM, pos, pos+len(plaintext)+8)

    return pos, ciphertext, hmac

The current offset into the key stream (pos), the ciphertext and HMAC can now be transmitted. Decryption and verification would work like this.

function decrypt_and_verify(pos, ciphertext, hmac):
    fp = open(KEYSTREAM)
    fp.seek(pos)

    cipherpad = fp.read(len(plaintext))

    macpad = fp.read(8)
    assert hash(ciphertext + macpad) == hmac

    plaintext = ciphertext XOR cipherpad

    return plaintext

Just to preempt some potential comments:

Yes, AES-EAX and the like may be a better solution.
The challenge of safely distributing the KEYSTREAM is no different from using any other shared secret unless a Key-Exchange Protocol is used.
Ideally the Encrypt-and-HMAC should be done inside an HSM module or the security could be easily compromised if someone gains access to the water meter.
Having a small number of compromised water meters may be an acceptable business risk akin to water meters that are simply faulty. This would eliminate the cost of the HSM module.
An interesting challenge arises if the payload size of the transmission channel is very small like in Sigfox (12 bytes) and the smaller packet size options of LoRaWan and Weightless. Could one transmit only the first few bytes
of the HMAC???

I am looking forward to your comments, feedback and criticism.

Two points adding to Raoul's answer are:-

To generate a HMAC you need a key, and this key will have to be stored within the meter.  If there's a key, traditional encryption can be used if you can somehow generate IVs.  Or don't generate them and accept that repeat readings will be transmitted as repeat cipher text.  This probably isn't a particularly serious issue for water consumption. Although, a static reading suggests the occupants are on holiday and the house is unoccupied. So this is an example of information leakage.
You compare OTP distribution to traditional key distribution.  That might be true but have you considered the office end?  This application of a OTP is about the worst possible kind.  OTPs do not perform well in many to one transmissions.  There will have to be a huge one time pad at the receiving station to decode readings from (100k+) meters. And how will you decode the reading if the meter ID is encrypted?  If you use an IP address as an identifier, that can be intercepted so what's the point of encrypting the meter ID?  And what happens if you roll out more meters?  More OTP material has to be stored, interwoven with existing OTP material and subsequently tracked at the base office.

In summary, this is not the most appropriate scenario for a OTP. But, it you only had one meter (for lets say a home automation system), OTP is perfect as it eliminates all the cryptographic code /testing issues.  Assuming of course that you can estimate the required pad size as Raoul suggests.


How can I create a block cipher of a reduced size given a fixed length block cipher? I've been reading papers on variable sized block cipher constructions based on fixed-length block ciphers, and they tend to focus on increasing the block size. They either gloss over or speak too generally about decreasing the block size. (Or I'm just not getting it, which is possible)

On the Construction of Variable-Input-Length Ciphers
Efficient Constructions of Variable-Input-Length
Block Ciphers

While these are certainly helpful, I also need a way to encrypt a size much smaller than the usual block ciphers. For example, a credit card has 16 digits, which can be represented in 54 bits. To encrypt a credit card number to another one would require a 54-bit block cipher. (The 54-bits could be brought even lower if you consider that the first and last digits are not random)

Is there a way to do this in such a way that the security isn't brought below the chance of simply guessing the plaintext?

If I understand your problem, I think the best way would be to pad the plaintext bits to 128 bits (8 bytes) with zeros and then use a strong block cipher like AES (Rijndael). Of course, then your ciphertext will be 128 bits instead of the 54 (or whatever) you started with. You can trim these trailing zeros after decryption.  If you want the ciphertext to be the same length, you'll have to use a stream method, but which will not be as strong.


Can I implement key recovery without compromising security? I'm no crypto expert but I'm trying to figure out if this is possible:

I'm building an application that has access to very sensitive user data.
I receive this data in plain text but I'm not allowed to persist it in this state.
When I receive data for user X, I must immediately encrypt the data using the key of user X. I can then persist the encrypted data.
User X needs to be able to grant the ability to decrypt their data to any other user in the system, for a defined period of time. All users in the system are trusted i.e. their identity is not in question.
The ability to decrypt user X's data can only be gained via user X explicitly granting permission i.e. even system admins should not be able to decrypt user X's data without permission being granted.

But, the most important part of all this is:

User X should be able to recover their key if they lose it. We can assume that I will have a solid multi-factor authentication flow to establish and verify the identity of user X.

So my questions are:

If a user loses their key, is there a way to recover their key without having to regenerate the key? So unlike the usual password-recovery flow, I'm not looking to simply regenerate a new key, because that would effectively orphan user X's data already encrypted with the previous key. Is this possible and/or feasible?
With [1] in mind, if an attacker gained full access to my database, is it possible to avoid keeping all the user keys in a central location that would expose me to this kind of attack?
How would I handle providing the ability to decrypt data to an arbitrary number of users without having to re-encrypt the data for each user? i.e. I will only ever have a single encrypted version of user X's data.

I hope this makes sense. I'm happy to try to provide a better explanation.

This answer feels very close, but I'm not sure it satisfies all my requirements: https://mathoverflow.net/a/62111

Any advice and/or guidance would be most welcome.

Delegating the decryption of encrypted data is exactly what proxy re-encryption (PRE) was designed to allow. In particular, there is a variant called time-based PRE that limits the delegation to a time period. See this paper for an example.

That doesn't really help with key recovery, though. You can encrypt the private key using a passphrase the user provides (run through a PBKDF function), but the user is still out of luck if she forgets the passphrase.


Any Arbitrary Function According to the attached reference, does it mean that the adversary computes $PPT(initial~input)$, $PPT(z)$ and $PPT(f_i(x',y'))$?

For example, suppose the corrupted party, in the malicious model, has inputs $x,z$ and it wants to compute $x \land y$, then the adversary's output will be:

$PPT(x)$, $PPT(z)$ and $PPT(x \land y))$. Am I right?

Note: PPT is a probabilistic polynomial-time algorithm

It means that the adversary can perform whatever (PPT) computation it wants based on all the information it has (namely, the corrupted party's input, the adversary's auxiliary input, and the value received from the trusted party) and output the result of that computation.


Bit Flipping Attack on CBC Mode To perform a bit flipping attack, the previous block is modified by using XOR. This results in an altered plaintext. However, now the ciphertext of the previous block is altered, hence it will result in an invalid format. Am I correct or am I missing something?

For example, suppose I have the following plaintext name=jcconvenant;photo=picture.jpg;admin=false;colour=red;

and the correspoding ciphertext c26a5697689463d662f540e55e2a1ecef9c5df20133dfe49d6d3c369679a95ff4f4c5a490f530b2a2f25db40da64f1e9302724ce61b9a435e23f4d600252a143

Suppose we perform a bit flipping attack and get the following ciphertext
c26a5697689463d662f540e55e2a1ecef9c5df20133dfe49d6c1d07071c495ff4f4c5a490f530b2a2f25db40da64f1e9302724ce61b9a435e23f4d600252a143

Then the resulting plaintext will still look corrupted.

¶ä╚°  h8ì│►Nƒz│Ioé¤ßkü2KÀQiý4I@pg;admin=true;;colour=red;

Is there a way to perform bit flipping while still obtaining a valid plaintext?

The Bit Flipping attack
Decryption process in CBC mode is performed as
\begin{align}
P_1 =& Dec_k(C_1) \oplus IV\\
P_i =& Dec_k(C_i) \oplus C_{i-1},\;\; 1 < i \leq nb,
\end{align}
where $nb$ is the number of blocks.
If you know the position of the target byte, then you can modify the corresponding ciphertext position in the previous ciphertext block. For example; if you modify a byte in the ciphertext $C_{i-1}$, then $P_i$ will be changed by one block since $C_{i-1}$ only affects the plaintext $P_i$ by $\oplus$. We can see visually in the below figure;

$\color{red}{\textbf{Red case:}}$ A ciphertext byte of $C_2$ modified. This affects the corresponding byte in the next plaintext block $P_3$ and the corresponding full plaintext block $P_2$ which has the same index as the modified ciphertext which is garbage. This can be seen as there is an error.
$\color{ForestGreen}{\textbf{Green case:}}$ an $\text{IV}$ byte is modified (green), this affects only the corresponding byte in the first plaintext $P_1$. If the target plaintext is in the first block, this will not leave a trace.
An example
Consider this simple message
msg = "Buy 1000 lots of waffles"
Now the attacker intercepts the message and now the default structure and want to modify it into
msg = "Buy 5000 lots of waffles"
Here is the sample Python code ( the full code is here );
def bitFlip( pos, bit, data):
    raw = b64decode(data)

    list1 = list(raw)
    list1[pos] = chr(ord(list1[pos])^bit)
    raw = ''.join(list1)
    return b64encode(raw)

With a call ctx = bitFlip(4,4,ctx) changes the 1 into 5.
This is the green case attack, that leaves no garbage block. Some file formats, like PDF, can live with the red case attack.
A Little Theory
CBC mode for encryption can only provide Ind-CPA security. CPA security doesn't resist active attacks, like CCA (See this post Ind- notions for details). Therefore an active attacker can modify the pure CBC ciphertext on their behalf. If the message format is known, this can cause devastating effects especially if the important part is in the first block.
The Mitigation
The attack is possible since there is no integrity and authentication on the data. A MAC or an HMAC can be used to prevent this like AES-CBC-HMAC if the CBC mode is a must to use.
In other cases, it is better to use modern encryption schemes. The authenticated encryption with Associated Data (AEAD) which provides confidentiality, integrity, and authenticity. The examples are AES-GCM and ChaCha20-Poly1305. In TLS 1.3., CCM,GCM, and poly1305 are standardized authenticated encryption modes.
There are alternatives to the above like AES-GCM-SIV which is designed to resist the (nonce,key) pair resue problem of the CTR based encryptions ( all of TLS 1.3 has) and xChaha20-Poly1305 that uses 192-bit nonces to reduce the chance of collision into very low probability.


Are (EC) DSA blind signatures possible? I've been searching for a way to create blind ECDSA signatures.
My research and experimentation has led me to believe that this is not possible.

I've been attempting to articulate why and I think that it is because it is not possible to apply a transformation to the message in a way which can be reversed whilst retaining a valid signature. The message and signature cannot be transformed as required because the ephemeral key is not known by the recipient, and if the key were known then the long term signing key could be determined. An ECDSA signature only permits validating that the signature was formed from the message and the private key corresponding to the expected public key.

I would like to confirm whether there are any known ECDSA blind signature schemes? I suppose publication bias might prevent this from appearing in the literature.

More generally are there any known ECDSA variants such as proxy signatures? My research has led me to the conclusion that it's functionality is entirely constrained to yielding a standard signature scheme.

I am not aware of any existing scheme allowing this easily (excepted for PureEdDSA maybe, but I wouldn't classify it as an ECDSA variant).

However I do not believe this is impossible. So let's try to do this for ECDSA:

We have a message $m$ whose hashed value $H(m)$ is converted into an integer $z$ which gets signed into the signature $(r,s)$ by the signer.

Now the verifier will basically rely on
$$\begin{aligned}
C&=u_1\times G+u_2\times Q\\
&=u_1 \times G +u_2d \times G\\
&=(u_1+u_2 d)\times G \\
&=(zs^{-1}+rds^{-1})\times G \\
&=(z+rds)\color{red}{s^{-1}}\times G \\
&=(z+rd)\color{red}{(z+rd)^{-1}(k^{-1})^{-1}}\times G \\
&=k\times G
\end{aligned}$$
And will say that it verifies iff $C_x==r$
And as you can see, if you can change $r,s,z$ then you can force a coefficient in the latest line to cancel "almost out", by taking $bs,abr,abz$ instead and would end up with $$(abz+abrd)\color{red}{b^{-1}(z+rd)^{-1}(k^{-1})^{-1}}\times G \\
= ak\times G $$

Now the difficult part is to find out if it is possible to get $a,b,m'$ such that $H(m')$, once converted into $z'$ is such that $z'=abz$ and such that $(ak\times G)_x \equiv abr\mod n$...

I do not see why this couldn't be possible, being given so much slack on the variables... But since I don't have time right now to actually try it out, I'll try to do it later or another day and will edit this answer accordingly.


How was the complexity of the Biclique Attack calculated? The abstract of the Biclique Attack paper claims:

  The first key recovery attack on the full AES-128 with computational complexity $2^{126.1}$.

What does $2^{126.1}$ mean in this context? And where does this value come from?

The usual convention on attack cost is the following: "the cost is N" means that running the attack, with a success probability of at least 50%, requires no more than:

N bits of memory space (RAM),
N plaintext/ciphertext pairs,
N*x clock cycles, where x is the number of clock cycles to compute one instance of the attacked algorithm (in the case of AES, "one instance" is encrypting one block).

The generic exhaustive key search (aka "brute force") on AES-128 has cost 2127, and that's entirely CPU cost (when trying many keys, you do not need much RAM, and one plaintext/ciphertext pair is sufficient). The cost is 2127 because trying out half of the possible keys is enough to make the success probability exceed 50%. Correspondingly, no attack can be deemed "real", in an academic way, unless it does better than that.

The biclique attack pretends to do better, with a cost of 2125.1, which is about 73% less than 2127 (if you prefer, the biclique attack is about 3.7 times more efficient than exhaustive key search). But note that nobody is talking about actually running it ! This kind of comparison is mostly formal, which is why we allow ourselves to consider that having N bits of RAM, obtaining N plaintext/ciphertext pairs, and computing N times the block encryption, have the same cost. This does not make practical sense.

(Note: in a previous version of this answer, I had used 2126.1, which is the figure with the article, but Christian Rechberger pointed out to me that it was computed for 100% success rate, and it scales like brute force. For 50% success rate, the complexity is 2125.1.)

For instance, buy a simple PC, and you'll be able to compute 248 AES encryptions per week, but 248 bits is 32 terabytes: that could prove a bit expensive. And convincing your target to encrypt 4096 terabytes worth of data might be somewhat challenging. That's comparing apples with oranges, and also with pickled herrings. Academics can get away with it because they are playing a game which has only indirect links with reality. It is about computing a lower bound for security.

When security is down to the realm of the potentially feasible, the proper measure is not the number of encryption or the RAM size, but the dollar.

Also, note that the biclique attack lowers security by less than two bits. This means that learning two bits of the key (by some leak) actually gives the attacker a bigger advantage than the biclique attack. This is why this attack is not scary. It is academically interesting, but not a danger in any way.


Second Preimages on n-bit Hash Functions by John Kelsey and Bruce Schneier I read your https://www.schneier.com/academic/paperfiles/paper-preimages.pdf

And found there:

«3.2 A Generic Technique: Multicollisions of Different Lengths»

    «Finding a Collision on Two Messages of Different Lengths.»

        «ALGORITHM:»

            «Steps:»

THIS:
"Build lists A and B as follows:"

– for i = 0 to 2n/2 − 1:
• A[i] = F(hin,M(i))
• B[i] = F(htmp,M(i))

There «i» takes value from 0 to 2^(n/2), BUT numbers of M’s blocks much less «2^(n/2)»
Maybe correct go through the cycle [0, 2^k] ? Otherwise, many of M(i) simply don’t exist.

or I'm wrong and something i don't understand?

P.S. Is there a chance, that won't find a collision in a range [0, 2^k]?

Thanks!

Ok, i figured out. I thought "M" - original message, but it's random data necessary for generation "Expandable Messages". In this case, range [ 0, 2^(n/2) ] is right.


Does Camellia-GCM use Camellia-CTR to create GCM Hash? I'm still confused when reading GnuTLS/Nettle implementation about Camellia-GCM.

Does Camellia-GCM use Camellia-CTR to create GCM Hash?

GCM is a mode of operation for a 128-bit blocksize block cipher that turns it into an authenticated encryption scheme. It doesn't care about whether you're using AES, Camellia, Twofish, Serpent or MARS. It will work the same way for all of these block ciphers. So yes, Camellia-GCM uses Camellia-CTR internally in exactly the same way AES-GCM uses AES-CTR internally. with Camellia getting the exact same inputs as AES.


Encrypt-then-MAC: full random keys or keys derived from master key? I have this scenario where I use Encrypt-then-MAC (AES256-CBC and HMAC-SHA256) with keys generated by a CSPRNG (specifically, SecureRandom in Java). I'd like to know which is better:

Use the CSPRNG to generate two distinct keys of 32 byte each

or

Use the CSPRNG to generate a master key of 32 byte and then use HKDF to derive the encryption and authentication key

I'd like to add that no human interaction is involved: this keys are stored inside a DB and are only used by machines.

Thank you very much!

If you are concerned about database size, only the master key needs to be stored when you use HKDF. Ditto when sending it to another computer. Otherwise, two independent random keys are clearly secure and simpler to implement, so you should do that.


Is the ChaCha20 block function reversible using known plaintext? I've been recently implementing the chacha20 stream cipher with Poly1305. As the core operations which make up the Quarter Round of chacha20 (ARX - Addition Rotation Xor) are indeed reversible, does that make reversing the ChaCha20 possible if an attacker knows the 512 bit key stream generated by the function, by a known plaintext attack on ciphertext that was generated by XORing the former keystream with the known plaintext?

I understand that the design of Chacha20 that uses the processor friendly ARX at its core, makes it very efficient, fast and secure, and hence widely adopted, and I'm also confident about the confusion and diffusion that it offers.

But,
Will it be reversible in the face of a Quantum Computer, if not by a classical computer?

Sorry if my concerns are naive!

The function which generates keystream blocks is based on a 512-bit permutation function. A permutation is, by definition, bijective.

The inverse of this permutation particular is trivial to implement in software. Just perform the individual operations (add, rotate, XOR) in reverse order, replacing modular addition with modular subtraction and reversing the direction of rotations.

Trying to reverse the entire keystream-block-generating function will fail, though, if the key is not already known. Actual keystream blocks are formed by combining  the input bits of the permutation with the output bits.1 Part of those input bits are key bits (which should be uniformly distributed and secret).

Since the permutation function scambles inputs so well, you can basically treat each input and its corresponding permutation-output as being statistically independent.

(Warning: Diliberate over-simplification. This is for illustrative purposes only. I don't want to say that "scrambling well" is sufficient. Or even that ChaCha's internal permutation is good enough to abuse in non-standard ways.)

If you change one input bit other than the key, then the output of the permutation will look completely different. When the secret key gets added back in, it obscures the value of the actual permutation output.

You would have to guess the 128-bit or 256-bit key before you could work backward even if you knew the full value of the keystream block in addition to the non-secret parts of the input vector. (The IV, counter, and constants. Adding these non-secret inputs to the permutation output does nothing to affect security, but it's included in the algorithm specification anyway for software efficiency reasons.)

One could almost make a stronger claim, that the keystream-block-generating function is one-way in the same way that hash functions are one way. Hash function design was actually a source of inspiration for ChaCha20's predecessor.

By one-way I mean there is no efficient algorithm to compute an input which produces an arbitrarily chosen output value. That's probably not possible (or at least is non-trivial) for any non-zero output block value.

The construction $F(x) = x \oplus P(x)$ should make $F$ a one-way function if $x$ has sufficiently many bits and $P$ were a random permutation. (Chosen uniformly from the set of all $(2^n)!$ possible n-bit permutations.)

Such a permutation would be unlikely to have any systemic relationship between input and output values. That thwarts the search for preimages for an ideal $P$. The same would be true if $\oplus$ were replaced with $\boxplus$.

We don't currently know an algorithm to find preimages for ChaCha20's hash-like operation, when we don't have foreknowledge of that preimage, with the exception of the value zero.2

That exception could be really important for some applications. So don't take the risk in adapting ChaCha to roll your own algorithm!

1. Specifically, ChaCha20 uses mod $2^{32}$ addition on the 16-word input/output vectors. It would also have worked if the design called for XORing inputs and outputs bit-for-bit, since both addition and XOR are non-linear with respect to the permutation function and neither operation should produce biased results.

2. ChaCha20 uses a pure ARX permutation. $F(0) = 0$ because $P(0) = 0$ because $0 \oplus 0 = 0, 0 \boxplus 0 = 0, \text{and}\ 0 \>>>> r = 0$.


Why is the Pedersen commitment perfectly hiding? I learned today about the Pedersen commitment scheme.

A quick reminder (I know there are some variants of this scheme, so I will present the one I learned about):

Public parameters - 2 primes $p,q$ such that $p=2q+1$, and 2 elements $g_1, g_2 \in \mathbb{Z}_p^*$ of order $q$ (i.e $g_1,g_2$ are generators of a q-ordered sub-group of $\mathbb{Z}_p^*$).
Secret parameter - $s \in \mathbb{Z}_q$
The scheme - $P$ chooses $r \in \mathbb{Z}_q$ at random and sends the commitment $C = g_1^s g_2^r \pmod p$. Then $P$ reveals $s',r'$ and $V$ accepts iff $C = g_1^{s'} g_2^{r'} \pmod p$.

I read that the scheme is perfectly hiding (i.e - even an unbounded adversary cannot reveal $s$ given only the commitment $C$). Why is that true?

When I was asked if even an unbounded adversary can learn anything, I thought that such adversary can iteratively try possible values of $r,s$ until he finds such values that satisfy $C = g_1^s g_2^r$ (I was apparently wrong of course). Why isn't that correct?

When I was asked if even an unbounded adversary can learn anything, I thought that such adversary can iteratively try possible values of $r,s$ until he finds such values that satisfy $C = g_1^s g_2^r$ (I was apparently wrong of course). Why isn't that correct?

Because there are lots of different $r, s$ pairs that satisify the solution.  In particular, for every possible $s$ value, there's exactly one corresponding $r$ value that satisfies $C = g_1^s g_2^r$.  Hence, an exhaustive search will not eliminate any possible $s$ values (or make any one more likely); hence, the adversary gets no information about $s$ from the value of $C$.

How this works may be easier to understand if we map this to an easier-to-understand group; if we select an arbitrary subgroup generator $g$, and have $g^a = g_1$, $g^b = g_2$, and $g^c = C$ (as $C$ must also be in the subgroup), the relation is $g^c = g^{as} g^{br}$ or $c = as + br \bmod q$.  We can rearrange this to $b^{-1}(c - as) = r$ (assuming $b \ne 0$; this cannot happen as $g_2$ was specified to be a generator), and so we can see that for a specific $s$ value, this gives us the unique $r$ value that satisfies the relation.

More precisely, the paragraph above (and in particular the equation $b^{-1}(c - as) = r$) shows us that for every value $s$ there is a unique value $r$ such that $C=g_1^s g_2^r$.

BTW: this is the same reason that One Time Pad is perfectly hiding.


How to solve this decryption algorithm given the encryption algorithm? Consider the following cryptosystem with plaintexts from the set $M$ and ciphertexts from the set $S$ with $M = S = \{0, 1\}^4$ . A plaintext $P = (P_1, P_2, P_3, P_4)$ is encrypted to a ciphertext $C = (C_1, C_2, C_3, C_4)$ as follows.
$C_1 = (a P_1 + P_2) \pmod 2$
$C_2 = (b P_1 + c P_2) \pmod 2$
$C_3 = (d P_3 + e P_4) \pmod 2$
$C_4 = ( P_3 + f P_4) \pmod 2$
The key is given as $k = (a, b, c, d, e, f)\in \{0, 1\}^6$, i.e., it holds $C = E(k,P)$.
a. Describe the decription algorithm.
b. Is the given system perfectly secure? Prove your answer.

I know that if $C_1 = a + P_1$ then $P_1 = a + C_1$. However because $C_1$ and $C_2$ use the same letters $P_1$ and $P_2$ (also in the case of $C_3$ and $C_4$), I don't know how to reverse them to get back $P_1$ and $P_2$

Here's a hint about the second part of the question:

b. Is the given system perfectly secure? Prove your answer.

Hint: what is the encryption of the plaintext $(0, 0, 0, 0)$?  If the ciphertext is something other than $(0, 0, 0, 0)$, what can we infer about the plaintext about that?


Monero Ring CT sj calculation For a university project, I am currently implementing the RingCT Ring signatures as  used in Monero (before the introduction of Bulletproofs) as laid out in this paper.
To close the ring we calculate the last $s$ like this: (where $\alpha$ is the random value initially chosen and $l$ is the order of the elliptic curve group)
$$s_j = α − c_j· x_j \bmod l $$

So as I understand the modulo in this case only applies to the $$c_j· x_j$$ otherwise we might get an out of range scalar, but then if this value is bigger then $\alpha$ it could happen that the $s$ is negative? Do I need another modulos here or do I understand something incorrectly?

All of the arithmetic is done modulo $l$ here.  The notation is slightly confusing—I would have written it as: $$s_j \equiv \alpha - c_j\cdot x_j \pmod l.$$  It may not actually matter whether the integer representative you choose for the scalar is positive or negative; there are many equivalent choices of scalar that will yield the same result when you multiply a curve point by them.  (But the specific algorithm you use to compute scalar multiplication may impose constraints on the integer, like being positive and below a certain size.)


Is there a kind of OS entropy pool on Windows systems? I am wondering if Windows provides an equivalent of /dev/urandom from linux ? Or any kind of system entropy pool ?

So far as I know, Windows does not (but you never know, it has an endless series of APIs so anything is possible). However, Intel hardware does. The Microsoft C/C++ compiler (and the Intel compiler) has intrinsics for obtaining a hardware generated random value. That value is obtained by running two circuits backwards so that are unstable. They generate a ton of very random bits which are then cleaned up. Intel has some white papers on it. I don't know if AMD processors have the same thing. I don't have either the name of the functions or the white paper handy, but you can find them with a web search (or, for the functions, look in the header files).


Combining CTR and ECB modes to prevent attacks In Reusing AES-CTR Keys and IVs for File Encryption, the OP was asking about a composite encryption scheme $$C_i = E_K\left(P_i \oplus E_K\left(IV + i\right)\right)$$ which is basically just a CTR followed an ECB.
Now, while their intent was to use this for disk encryption (where the IV is just the unique (but known) location of a block on disk), this approach came with certain weaknesses due to the attack capabilities of an attacker in disk encryption theory. However, I was wondering if there are significant advantages to this CTR-then-ECB outside of necessarily a disk encryption context -- such as encrypting data in a database, for example.
Specifically, any reuse of (IV/nonce + counter) in CTR (for the same key) can trivially lead to a known-plaintext attack if the attacker knows the plaintext of any other blocks also encrypted with that (IV/nonce + counter). And not only just one (IV/nonce + counter) block, but also any "nearby" blocks belonging to those messages as well (due to counter overlap!).
However, if we encrypt with CTR-then-ECB, then the attacker will only know the plaintext of blocks if they are encrypted with the same IV+counter and also contain the same ciphertext as well. In contrast, an attacker of a CTR-only encryption scheme requires only matching IV + counter (to a known block), and an attacker of an CBC-only encryption scheme requires only matching ciphertexts (to a known block).
But is this a significant advantage, or are the probabilities involved here so minute -- especially if using random IV's -- that CTR-then-ECB fails to provide any real benefit? (for example, with AES)

There are a few problems that spring to mind:

this is a double-pass scheme, which is computationally expensive;
the leakage of blocks that are identical is unnecessary, there are schemes that only leak fully identical plaintext;
ECB mode requires padding, so you would create some overhead.

Now you could argue that 1. is not a problem on current computers. However, that would only be a good argument if there weren't any schemes out there that would present the same properties without requiring a double pass.
As for 2, there are schemes such as Format Preserving Encryption that don't leak any information other than fully identical plaintext. FPE is generally rather expensive when it comes to implementation (on the other hand, not having to store an IV is generally not a problem for large binaries as they would generally have a VARiable size). Another option is to perform a block encrypt on the index and use that as unpredictable IV for CBC mode (possibly with ciphertext stealing if you don't like the padding overhead). Existing disk encryption routines such as XTS and ESSIV have already been mentioned.
As for 3, ciphertext stealing (CTS) for ECB mode can of course be implemented, but it definitely doesn't help with ease of implementation, which would be the major benefit over other schemes (ECB is generally available in e.g. SQL, and CTR is relatively simple to implement using ECB, although I definitely would not like doing so in SQL).
Finally, if you have room for an authentication tag, then a SIV mode (such as AES-GCM-SIV) could be used to remove the need for an explicit IV. If you've got room for both then just a generic AES-GCM would make sense of course.
All in all, I think that - while the scheme has merits - there are better options out there - preferably ones that are build into the DB engine.


Information theoretical security of an inefficient Shamir based access structure I have studied Sharmir's scheme as well as the multiple assignment scheme proposed by M. Ito. My question is if anyone can tell me if the following scheme is theoretically secure:

Terms:

P = set of participants

B = Access structure

A = Access set (authorised set within access structure)

t = cardinality of Access structure (|B|)

d = cardinality of Access set (|A|)

S = the secret

So the scheme is extremely inefficient in that it involves creating exactly t different (d,d) Shamir schemes, such that there will be t different randomly chosen polynomials that all share the same secret s

Edit:
So the scheme is an access structure secret sharing scheme, basically it defines certain subgroups of a group of participants that are valid and can therefore reconstruct a secret.

For instance if there was a group of people p1,p2,p3 and an access structure of {p1p2, p1p3} then only the combination of p1 and p2 or p1 and p3 should be able to uncover the secret. so p1p2 and p1p3 are valid subgroups and p2p3 is an invalid subgroup and should therefore not be able to uncover the secret.

This scheme is theoretically insecure if an invalid group can uncover any information.This includes uncovering or computing a number that is NOT S (the secret) and knowing that this number is not the secret. so if p2p3 compute their shares and find a number S' that they know is not the secret then the scheme is insecure!

Example:

Let S = 6, P = {P1,P2,P3}, B = {P1-P2,P1-P3) such that P1 and P2 can find the secret as well as P1 and P3

Now we generate 2 shamir schemes with the same secret:

f1(x) = 6 + 4x

f2(x) = 6 + 7x

so we need two shares from each scheme:

s1, s2 = (1,10) and (2,14)

s'1, s'2 = (1,13) and (2,20)

P1 gets s1 and s'2

P2 gets s2

P3 gets s'2

Can anyone think of any reason as to why this scheme is not theoretically secure, it is very inefficient but as far as i know it is secure, i just don't know how to prove or disprove it.

many thanks

Yes, your scheme is trivially correct and secure.  This follows from the fact that:

Shamir's secret sharing is correct: any group of participants with at least the threshold number of shares can reliably reconstruct the secret; and
Shamir's secret sharing is perfectly secure: no group of participants with less than the threshold number of shares can learn any information about the secret.

Since your subschemes are constructed independently except for having the same secret, the only way in which knowledge learned from one subscheme could help in breaking another subscheme is if this knowledge somehow involved the secret.  But since Shamir's secret sharing, by construction, reveals no information about the secret without access to the threshold number of shares, this is not possible.

Another way to show this is to assume that a group already has, for each subscheme, access to just one less share than the threshold number for that subscheme.  (We can do this without loss of generality, since giving an attacker access to more shares never hurts their chances of recovering the secret.)  Then show that, for any possible secret value, there exists a unique assignment of the missing shares for each subscheme that will reconstruct that secret.  (This is basically the standard proof for the security of basic Shamir's secret sharing, just with multiple sets of shares and polynomials.)

Also note that, since your subschemes are always $(n,n)$ schemes (i.e. they always require all shares to reconstruct the secret), you don't actually need the full power of Shamir's scheme.  In particular, trivial secret sharing, e.g. based on XOR or modular addition, would work just as well.


What time is used in a TOTP counter? I am currently working on a desktop TOTP client.

From the TOTP spec at https://tools.ietf.org/html/rfc6238#section-4.1, the 6 digit  OTP is generated from counter (in this case time).

But what is "time"? The spec says that the time is in the format of a Unix time epoch (seconds that have elapsed since Jan 01 1970).

My question is,

What how do I compute this Unix time?

a) Do I get UTC time & convert it to Unix time epochs?
b) Do I get local time & convert it to Unix time epochs?

or

c) Converting both UTC & local time to Unix time gives the same value so it will not matter?

I think this simply comes down to the definition of Unix time, which is given in the Wikipedia article:

  Unix time (also known as POSIX time[1][2] or UNIX Epoch time[3]) is a system for describing a point in time. It is the number of seconds that have elapsed since 00:00:00 Thursday, 1 January 1970,[2] Coordinated Universal Time (UTC), minus leap seconds. Every day is treated as if it contains exactly 86400 seconds,[2] so leap seconds are to be subtracted since the epoch.

Although I would have described it as "without taking leap seconds into account" myself. Generally you should be able to get the Unix time from some time API or old API function, but otherwise (a) seems to be most reasonable. The Wikipedia article also contains ways of converting from different time formats, specifically UTC.


TLS Handshake : Server authentication or only Server ‘s Certificate authentication? I have some difficulty understanding the way in which the Server is really authenticated by Client in TLS handshake (in case of using RSA key exchange).

When Client receives Server ‘s Certificate and verifies it with using CA root public key, I fully understand that at this time, Client can consider that such received Certificate is valid and authentic if verification is ok

But if Server’s certificate is checked sucessfully by Client, how is it possible to consider that Server has been authenticated by Client, while at this time none message signed with Server’s private key has been sent to the Client and verified by it ? Can’t intruder possess and send real Server's certificate to the Client ?

Note : I agree that if Server is not the real one and so doesn't possess real Server private key, it will not be able to decrypt the pre-master key sent by Client, but this appears as indirect / implicit authentication, rather than explicit authentication

More generally (outside case of TLS), is it correct to talk about « Authentication by Certificate » (assuming based on Certificate verification via CA root public key)  instead of  authentication via digital signature ?

But if Server’s certificate is checked sucessfully by Client, how is
  it possible to consider that Server has been authenticated by Client,
  while at this time none message signed with Server’s private key has
  been sent to the Client and verified by it ?

If only consider the key exchange to be what the RFC says it is, then yes this key-exchange can be broken by an attacker having the right certificate.

However this is not how TLS works in practice. In practice you'd never stop after the ClientKeyExchange message as you have set-up the connection to actually do something. This is why most formal analysis considers ChangeCipherSpec and the Finished messages as part of the key-exchange for their proofs.
And it only matters that the server is successfully authenticated after they complete key-exchange, not at some "randomly chosen" point in the protocol.

The exchange turns out to be secure and properly authenticated by verifying the Finished message which contains a MAC on all previous (handshake) messages. Because a fake server can't decrypt the pre-master secret and hence can't compute the master secret, he can't compute the neccessary MAC and the client will respond with a fatal_alert, killing the connection.

I don't know why the designers of TLS chose this "through the backdoor" authentication method but I can only guess they wanted to avoid yet another computationally intensive private key based operation for the server.

TL;DR: The finished message gives you authentication with its MAC only being available to the private key holder.

  Is it correct to talk about "Authentication by Certificate"
  (assuming based on Certificate verification via CA root public key)
  instead of authentication via digital signature?

You never authenticate by only presenting a certificate.
The only situation where you may do it is with secure tokens holding key-files to access some physically restricted facility where the tokens will never actually be plugged into a real computer (aside from new file assignment).

In an internet-based scenario you'd never do this as every eavesdropper could impersonate the owner of the certificate, rendering it completely useless.

What TLS does (and may be meant by your question) is encryption-based / certificate-based authentication. This is basically some sort of challenge-response protcol, where you send some party a random nonce and an asymmetrically encrypted key and expect the MAC on the nonce using that key as response. One can do that, but this is rather "abusing" the encryption to do things it was not intended to, as we have dedicated constructions for that: digital signatures.
So usually a designer would rather go with a digital signature and an encryption ( / decryption) (or even better DH) as today it's pretty cheap to do both operations, whereas you may need to use the encryption based approach for very constrained devices where only one such operation is "allowed" / feasible or where actually can't perform signatures (by padding, rather unusual).

TL;DR: Solely certificate based authentication is bad and only feasible in physical access restriction scenarios and otherwise you can do challenge-response with encryption but should prefer signatures.


Modification of block cipher in CBC mode I know that CBC is not secure against data modification. Can someone explain to me by illustrating at an example how I could change the last block if I have the encryption of "0"?

Thanks in advance

If you flip bits in cipher text block $E_K(M_i)$ then you flip the same bits in $M_{i+1}$. If you know or guess the value of the last plaintext block then XOR the second to last ciphertext block with the guessed plaintext value. That makes it zero because $v \oplus v = 0$ for all v. It's not so easy to manipulate otherwise.

Edit: I misread encrypted "0" as set plaintext to zero

If $M_i$ is known to be zero then XORing $M_{i-1}$ with $v$ causes block i to decrypt to $v$ instead.


What may be causing conflicts in Whirlpool implementation versions? I see by layman articles (e.g. at Wikipedia) that the Whirlpool hash function has seemingly three current versions. That is to say, they are referenced as Whirlpool-0 (original reference code), Whirlpool-T, an optimised for hardware version which was changed to whirlpool (let’s call it “current”) due to a somewhat weakening in a diffusion matrix (according to article).

Now, I see some python implementations do indeed use that “current” version. However, I have been using librhash on Linux (i.e. rhash -W \$file) and I’m verifying things with OpenSSL (openssl dgst -whirlpool \$file).

OpenSSL and rHash are consistent with each other, but different from the current version. I also noticed that OpenSSL and rHash do not seem to correlate to either of the previous versions.

Why is this so? Has there been some undocumented update to the default Whirlpool s-boxes or something? Is there a version conflict, or has there been a Whirlpool update I may have missed?

There is no difference.

The wiki page you referred to contains examples of hashes for all three versions of Whirlpool. For string "The quick brown fox jumps over the lazy dog", the current version should produce the following hash:

    B97DE512E91E3828B40D2B0FDCE9CEB3C4A71F9BEA8D88E75C4FA854DF36725F
    D2B52EB6544EDCACD6F8BEDDFEA403CB55AE31F03AD62A5EF54E42EE82C3FB35

Let's create a file containing this string and test different implementations.

    $ openssl dgst -whirlpool quick.txt
    whirlpool(quick.txt)= b97de512e91e3828b40d2b0fdce9ceb3c4a71f9bea8d88e75c4fa854df36725fd2b52eb6544edcacd6f8beddfea403cb55ae31f03ad62a5ef54e42ee82c3fb35

    $ rhash -W quick.txt
    b97de512e91e3828b40d2b0fdce9ceb3c4a71f9bea8d88e75c4fa854df36725fd2b52eb6544edcacd6f8beddfea403cb55ae31f03ad62a5ef54e42ee82c3fb35  quick.txt

Both match the hash from the wiki.
Let's test the python implementation using this script:

    import whirlpool

    wp = whirlpool.new("The quick brown fox jumps over the lazy dog")
    hashed_string = wp.hexdigest()

    print(hashed_string)

The output is:

    b97de512e91e3828b40d2b0fdce9ceb3c4a71f9bea8d88e75c4fa854df36725fd2b52eb6544edcacd6f8beddfea403cb55ae31f03ad62a5ef54e42ee82c3fb35

Let's test the reference code from the Whirlpool home page by inserting the following lines at the end of makeISOTestVectors() function:

    const char* quick = "The quick brown fox jumps over the lazy dog";
    NESSIEinit(&w);
    NESSIEadd(quick, 8*strlen(quick), &w);
    NESSIEfinalize(&w, digest);
    printf("The hash-code is the following 512-bit string.\n\n");
    display(digest, DIGESTBYTES); printf("\n\n");
    fflush(stdout);

The output is:

    B97DE512E91E3828 B40D2B0FDCE9CEB3 C4A71F9BEA8D88E7 5C4FA854DF36725F
    D2B52EB6544EDCAC D6F8BEDDFEA403CB 55AE31F03AD62A5E F54E42EE82C3FB35

All implementations produce the same hash. Where did you found a mismatching version?


Properties of a single-message protocol using AES The following protocol is used for providing data confidentiality between sender and receiver:

$$ \text{sender} \rightarrow \text{receiver}: E_k(m \mathbin\Vert \mathrm{ID}_s\mathbin\Vert \mathrm{Timestamp}) $$

$E_k$: the encryption function of AES
$k$: a shared secret key
$\mathrm{ID}_s$: the ID of sender
$\mathrm{Timestamp}$: the time
$m$: the message (payload) from the sender

Assume that AES is secure. What are the security services that can be provided by this protocol?

I think we can get the Sender authentication because of the sender ID. But how about the others like data integrity, non-repudiation or data authentication? Can AES and this protocol provide this?

Non repudiation : No, as the sender can claim that the other person sent himself the message
Data Integrity : No, as the cipher text can be corrupted in the midway
Authentication : Yes, the message is indeed sent by other sender as the key is known only to sender and receiver
Confidentiality: Yes, as the key is only known to receiver and sender

Hope this helps


Algorithms for Cyrillic encryption I am working on a cryptography application which is to be used in my country. I tried looking up to see if there are any algorithms that support the Cyrillic alphabet, but I found none. Do you know of any? Can mainstream algorithms (Like AES) work with Cyrillic letters?

Modern cryptographic algorithms are specified in terms of bytes or even bits, not characters.
Whether the data you encrypt happens to represent latin or cyrillic letters or pictures or audio data or anything else does not matter at all to an encryption algorithm; all it ever sees is a bunch of bytes.

What this means in practice is: You have to fix some encoding (UTF-8 is very common nowadays) to translate your characters to a string of bytes which can then be processed by any cryptographic implementation as usual.


Non interactive ZKP that encrypted additive elgamal message is in set of valid messages This is taken from Anonymous voting by two-round
public discussion by F. Hao P.Y.A. Ryan P. Zielinski

Votes are encrypted using the additive variant of ElGamal. I am also using ECElgamal. The idea is that to vote for a particular candidate, you set your message as one of the following $v$ calculated below.

One problem is that if the voter sends a vote not specified in the valid set of $v$'s, then the resulting sum of $v$'s would affect the tallying of votes. For example, if you vote using $2\times2^0$, you are able to vote to candidate 1 $2$ times which not ideal. Or $2\times2^m$ to vote for candidate 2 twice.

How would one verify that the vote that is recorded (which is encrypted) is in one of the valid $v_i$ without decrypting the ciphertext of the vote or showing $v_i$?

The standard solution is to use a proof of encryption of zero, coupled with an or proof and a careful choice of ciphertexts.

A proof of encryption of zero is a proof that the decryption of a ciphertext is zero. For ElGamal, this is typically done using a proof of equal discrete logarithm. Recall that an encryption of zero is of the form $(x,w) = (g^r, y^r g^0)$, where $y$ is the public encryption key, so all you need to prove is that $\log_g x = \log_y w$. (This equality of d.log. proof is standard, I believe it is called Chaum-Pedersen or something. It essentially amounts to a Schnorr proof in a carefully chosen group.)

An or proof allows you to prove that one out of several claims is true. In this case, we consider the claims that several different ciphertexts are encryptions of zero, though only one will be. (Again, this is a standard technique for sigma protocols, which the above proof of encryption of zero is. It dates back to the 90s.)

Now, which ciphertexts do you apply the or proof to? You want to prove that $(x,w)$ is an encryption of $v_1$, $v_2$, ..., or $v_L$? Then you apply the or proof to the ciphertexts $(x,w g^{-v_1})$, ..., $(x, wg^{-v_L})$. If the encryption is valid, one of them will be an encryption of zero, allowing you to complete the or proof.


Random numbers for Rabin-Miller primality tests I've implemented a Rabin-Miller primality test fuction following Wikipedia and the book Applied Cryptography. Now I'm using it for generating primes with a string seed. The book suggests the following for this:

Generate a random 'n'-bit number
Set the high- and low-order bits to 1.
Make sure it is not divisible by small primes $p\in[2,2000]$.
Perform a Rabin-Miller Test for some random $a$. Choose a small value of $a$ to make it go quicker. Do five tests (I'm doing 40 as a post suggested here, and instead of generating a random number, I increment by one and test again.

So, first I used a random generator with uniform distribution to generate $a$, but after reading this, I changed it to the standard C++ rand() with srand(time(0)) seed. It is faster, but I'm not sure if it is the best way. Using boost's Twister was slower, but gave a wider range of $a$. I have searched (maybe not with right keywords) but how does choice of $a$ influence the test?

Is it good if the range is pretty small compared to the size of the number I test (saying $a$ is 32 bits, and the number is 512 bits)? Will it increase the odds of a false positive (pseudo prime)?

The fundamental property of the Rabin-Miller primality test is that, if the value $N$ being tested is composite, then it will return "composite" at least 75% of the time.  That is, if we define the function $RabinMiller( N, A )$ that runs the Rabin-Miller test against the number $N$, using $A$ as a witness, then for any composite $N$, $RabinMiller( N, A )$ will evaluate as "Composite" for more than 75% of the values of $A$ in the range $[2, N-1]$.

So, you question is "what happens if we don't chose $A$ uniformly from the range $[2, N-1]$; what happens if we chose $A$ from a much smaller range?

The answer to that is that nobody really knows; we know that at least 75% of the numbers in $[2, N-1]$ will reveal $N$ to be composite, however there are no proven results how they might be distributed (there is a proof if we assume an unproven conjecture within number theory, but until we get a proof of that conjecture, it doesn't count).  It would appear to be reasonable to conjecture that they are, in fact, reasonably well distributed, however we don't know that.

Hence, if you select your value $A$ from a smaller range, then while you probably have a good test, you have just voided the probabilistic provability that Rabin-Miller gives you.

In addition, there is also this fact that works in your favor; the Rabin-Miller proof states that, for any fixed composite $N$, that at least 75% of the values $A$ will return "composite", however for a random composite $N$, then $A$ will return "composite" almost all the time.  While there are certain composite $N$ where a random $A$ will have a $\approx 25$% chance of returning "probably prime", however those $N$ values are rather rare (significantly rarer than primes).  What this means is that, in practice, Rabin-Miller works significantly better than the proof would suggest.

So, that's the bottom line?  Well, if you're interested in retaining the provability aspect of Rabin-Miller, you rather have to select values from the full range (and it's not all that expensive when compared to running the Rabin-Miller test).  On the other hand, if you just want something that is likely to work, selecting from a smaller range is, as far as we know, reasonable.


Why are security against eavesdropping and security against CPA equivalent in the setting of public-key cryptography? Why are security against eavesdropping and security against CPA  equivalent
in the setting of public-key cryptography?

Under a chosen-plaintext attack, the adversary has the power to encrypt polynomially-many chosen plaintexts. In the symmetric world, since only the valid parties hold the encryption key, only the valid parties can "grant" the adversary access to an encryption oracle. So, it isn't assumed that an eavesdropper necessarily has access to an encryption oracle.

In the asymmetric world, however, the public key — the key used to encrypt data — is, well, public. So, an eavesdropper overhears the public key (or is simply assumed to know it, since it is public), and from there the eavesdropper may encrypt whatever messages he or she so desires. This is the same scenario as a chosen-plaintext attack.


can i find the algorithim of a prng by entering previous sequence Is there any software or can i find it manually the algorithm of a prng by entering previous sequences of results. there is 38 possible outcomes and results can repeat.

If the PRNG is a cryptographically secure PRNG, then no. A basic property of CSPRNG is that if you know all the bits of a sequence of outputs except one, then your probability of guessing that one bit is no better than pure chance.

A deterministic CSPRNG operates by having a secret state. Without finding out the secret state, there's no way to guess outputs.

If the PRNG is not cryptographically secure, then it might be possible to reconstruct some outputs knowing others. In fact that possibility is basically the definition of not being cryptographically secure. Realistically, unless the PRNG is extremely bad, it's rather difficult to find the algorithm given only a few outputs, but it might be very easy to find if you manage to guess the algorithm. Maybe it's a common one?


How many bytes of the last keystream block are used to XOR the final block of partial plaintext in CFB, OFB & CTR modes? I apologize if this is a dumb question but I'm trying to understand how the final block of partial plaintext is XORed using only n number of bytes in the final keystream block.

How do we determine the number of bytes in the keystream that are required to produce a final block of the same size (128 bit) as the others?

Suppose a block is $b$ bits long, say $b = 128$, and the message is $\ell$ bits long, say $\ell = 187$.  Then the final plaintext block is $n = \ell - \lfloor\ell/b\rfloor \cdot b$ bits long.  So use $n$ bits of the final keystream block; in this example, $n = 59$.


How to mix external entropy to a random number generator? For security personalization of a device within the production environment our customer requires the following:

  The private / public key pair should be placed within the device and
  within the Secure process environment.

  To generate the private key, parts of the entropy are to be generated
  by an external random number generator.

  Corresponding random data should be imported into the device.

I understand what they want but have no idea, how this additional entropy could be combinded with the device internal true-random-number generator. I understand, that a number of external generated random numbers should be combinded with the internal generator to yield the random numbers on which my private keys shall be based. How is this done in practice? To take the first 16 numbers from the internal and the other 16 numbers from the external source would be by far too trivial.

Based on the current details, this will work where I = internal generator and E is the external one:-

random bytes = I ⊕ SHA1(E)

The equation assumes that I is a good quality RNG.  The key here is to get enough entropy from E.  You should measure it's (min.)entropy generation rate in bit/s sample and then take enough samples to ensure you have F times 16 bytes of it.  F is a safety factor which ideally should be >2 but I'd just go with F = 100.  If you have an analogue entropy source you can easily get 10 kSa/s with an on chip ADC, and a digital entropy source can be sampled at something in the order of 10 MSa/s.  Depends really on the features of your micro controller.

The hash allows a dissimilar amount of entropy to be easily combined.  It also acts as a randomness extractor for E, so you don't have to be debias the entropy and it'll deal with huge auto correlation.

Note.  I would make the argument that there's no point in having the internal generator (I).  If you have the luxury of a true entropy generator, use it.  The hash extractor function means that additional whitening is not necessary.  As Shane tells Joey, if you can use it, one's all you need.  And how would I be seeded anyway?


Why is ElGamal considered non-deterministic? One difference between RSA and ElGamal is that ElGamal isn't necessarily deterministic (while RSA is).

What makes it non-deterministic? Is this advantageous to security? How else does this property affect ElGamal encryption or the ElGamal signature scheme?

In this context, "nondeterministic" means that the algorithm to generate the ciphertext (or the signature) takes a random value as one of its inputs, and it can generate many possible ciphertexts (or signatures) based on the random value.  ElGamal is nondetermanistic because the encryptor selects a random exponent as a part of encryption method.

For public key encryption, this randomization of the encrypted message is important.  If the public key encryption algorithm was not nondetermistic (that is, the encrypted message depended only on the plaintext message and the public key), then someone with an encrypted message $M$ and the public key $PK$ and a candidate plaintext message $P$ could test if the decryption of $M$ was $P$ (simply by encrypting $P$ using the public key $PK$, and checking if the result was $M$).

Because of this, public key encryption is almost always nondetermanistic.  Note that RSA is not an exception; while the core RSA algorithm is determanistic, actual RSA public key encryption also includes a padding method, and this padding method can (and generally does) include randomness.

For public key signatures, there is no corresponding requirement due to the primitive semantics that signatures be generated using some random input; however, some cryptography proof techniques do assume that the signature generation is also nondetermanistic.  On the other hand, in the specific case of ElGamal signatures (DSA), it actually does require a random input, and it turns out that this input really does need to be random, and uniformly distributed.


Zero knowledge proof for Paillier addition under multiple keys Suppose $m_0, m_1, m_2 \in \mathbb{N}$ such that $m_0 = m_1 + m_2$, $m_i > 0$ (none of them can be 0 or lower)

Under a Paillier cryptosystem, set

$e_0 = E(m_0, r_0)$ for a public key $(g_0, n_0)$
$e_1 = E(m_1, r_1)$ for a public key $(g_1, n_1)$
$e_2 = E(m_2, r_2)$ for a public key $(g_2, n_2)$

Can I prove (to a 3rd party, the verifier) that $m_0 = m_1 + m_2$ (or rather the equation with its encrypted counterparts hold) without revealing either of $m_0, m_1, m_2$ nor the private keys?

I, the prover, know all $m_i$, all public keys $(g_i, n_i)$ (by extension, also all $e_i$) and finally the private key $(\lambda_0,  \mu_0)$ for $(g_0, n_0)$ but not for the rest. Also, I as the prover get to choose all $r_i$

If all $e_i$ where encrypted under the same pubkey $(g,n)$, then I know we could check if $e_0 \cdot (e_1 \cdot e_2)^{-1}$ is a power of $n^2$ (as that evaluates to the encryption of 0), but it is not the case under diferent $(g_i,n_i)$.

Take $(\cdot)^{-1}$ as the modular multiplicative inverse, thus emulating the subtraction in Paillier.

I might use other cryptosystems (ie. ElGamal) as long as they have homomorphic properties

As far as I know, with the same public key $(g,n)$
I would change the problem to prove that if
$e_0 = E(m_1,r_1)\cdot E(m_2,r_2)$
then $m_0 = D(e_0) = m_1 + m_2 \bmod n$ where $D(e_0)$ is the result of decrypting ciphertext $e_0$. Thanks Geoffroy for your helpful comment and LaTeX conversion regarding my incorrect guess on the use of html here. .


Is Ring-LWE now (2021) broken? A recent (29 Mar 2021) article "Ring-LWE over two-to-power cyclotomics is not hard" by Hao Chen is available in pre-print here: https://eprint.iacr.org/2021/418
I'm not a cryptographer. Does this article mean that Ring-LWE is unsuitable for post-quantum asymmetric cryptography? Does this means that others algorithms might be similarly affected? Or is the author somehow wrong?

Update: 20210403
TL;DR

If correct, the paper would affect the security of a wide range of RLWE systems, including all of the most commonly used variants.
However, the paper violates a "no go" theorem of a reviewed and established paper by Peikert.

Putting to the side the question of whether the paper is correct or not, there are RLWE instances that do not take place in power of two cyclotomic rings (although it is by far the most popular choice). For the NIST process it is worth noting that both CRYSTALS submissions (KYBER and DILITHIUM), FALCON and SABER all do use power of two cyclotomic rings. NTRU however uses $x^{509}-1$, $x^{677}-1$ and $x^{821}-1$, NTRUPrime does not even use a cyclotomic ring.
Thus even if the claims are met, they do not break all ring lattice systems, nor even all NIST ring lattice candidates.
(Technically the NTRU and LWE problems are distinct, though both are solved in practice by solving SVP/CVP instances, so I'll abusively elide the difference between RLWE and ring lattice instances).
The paper claims to break  decisional RLWE (distinguishing $(\mathbf a, \mathbf {as}+\mathbf e)$ from $(\mathbf a, \mathbf b)$ as opposed to recovering $\mathbf s$ and $\mathbf e$) in power of 2 cyclotomic rings. It then claims a quantum attack on a short sub-basis question. By section 5 of the LPR paper a decisional RLWE method would convert to a search RLWE method on cyclotomic rings (thanks to Mark and Chris Peikert for pointing out this reduction). This observation is not made in section 3.4 of Hao Chen's paper.
In terms of the distinguishing attack, the nub of the idea seems to be that we can find a sublattice $\mathbf L_2$ which contains both an ideal lattice $\mathbf Q$ that is dense enough that quite a few random elements end up in there and another sublattice $\mathbf L_1$ where error vectors have an elevated chance of appearing (e.g. the chance of an error vector appearing in $\mathbf L_1$ is twice the chance of a random vector appearing in $\mathbf L_2$). Then, if given a large collection of $(\mathbf a,\mathbf b)$ pairs from which we must guess the ones where $\mathbf b$ was generated from $\mathbf b=\mathbf{as}+\mathbf e$ we specialise to the subset where $\mathbf a\in \mathbf Q$. If generated via RLWE then $\mathbf{as}\in \mathbf Q\subset \mathbf L_2$ by the ideal property and $\mathbf e\in \mathbf L_1\subset \mathbf L_2$ with elevated probability, thus $\mathbf{as}+\mathbf e\in \mathbf L_2$ with elevated probability. If we therefore pick the $(\mathbf a,\mathbf b)$ pairs where $\mathbf a\in Q$ and $\mathbf b\in L_2$ and declare these to be RLWE instances, we would be more likely to be correct. Cyclotomic lattices do lend themselves to a wide choice of $\mathbf Q$.
However, lattices such as $L_2$ cannot exist for worst case error distributions. Section 5 of the Peikert paper linked in the TL;DR shows that if $\mathbf Q$ is dense enough to contain many $\mathbf a$, then the distribution of errors for worst case error distributions is smooth (i.e. does not have elevated probability) in $\mathbf Q$ and hence $\mathbf L_2$. Provably-hard ring LWE instances will usually have some reduction to worst case error distribution.
The "no go" observation is due to Chris Peikert and is largely taken from his twitter feed as linked in the paragraph above. Any errors and misrepresentations are due to me.


About integer factorization Let $N=pq$ where $p$ and $q$ are safe primes. If the adversary knows the inverse of $p$ mod $q$ and the inverse of $q$ mod $p$, can this help him factor $N$ or break the textbook RSA?

Santanu Sarkar and Subhamoy Maitra show in Some Applications of Lattice Based Root Finding Techniques the deterministic polynomial time equivalence between factoring $N$ ($N=p\cdot q$, where $p>q$ or $p,q$ are of same bit size) and knowledge of $q^{−1} \bmod p$ (cited from the abstract).


Current situation of bilinear pairing protocols The bilinear pairings are considered as the key enabler for many novel cryptographic protocols, such as three-party one round DH[1], shorter signatures and certificateless (ID-based) crypto[3] , which employ Tate and Weil pairings. Lots of promising research and progress has been made in the last decade, and the pairing concept has been hyped quite a bit.

However, there are also some sources claiming that pairings are "useless", for example this article from 2015: On the Disadvantages of Pairing-based Cryptography from university of Shanghai.

As a summary, the article claims that BPC (Bilinear pairing crypto) doesn't bring any advantage, and in fact requires significantly large key sizes. But the article only seems to consider Tate and Weil pairings, and only the short signature protocol.

Also, I haven't somehow found much new research or progress about current situation of pairing concepts from the past 5 years. I assume that at least pairings utilizing Tate and Weil are obsolete, as Ate and optimal Ate over BN-curves have turned out to be much more efficient.

So finally my question is: Are the bilinear pairings still considered useful, and what are the main advantages? I have assumed that they are so far the only way to implement protocols such as ID-based cryptography.

Sources:
A. Joux, (2000) “A one round protocol for tripartite Diﬃe-Hellman”
D. Boneh and M. Franklin,(2001) “Identity-based encryption from the Weil pairing”

That paper is misleading in several ways:

The DSA vs BB comparison: it is unfair because it compares DSA with the "full" BB scheme, which does not produce shorter signatures. The same BB paper describes a "basic" scheme that has a signature that is half the size of DSA. That's the whole point of short signature schemes (being shorter than ECDSA/DSA). This point is now moot, however, since a 2015 paper describing an attack that required pairing-based crypto to increase its parameter sizes, making short signatures not that short anymore (which does support the authors' claim, but that was not the justification they used).
They estimate that BB is 60 times slower than DSA but give no justification. While signature verification will indeed be slower, signing should be faster.
They raise the issue of the master key in PBC schemes. This is true, but only applies to ID-based crypto, and was known from the start.

Pairings are still relevant because some schemes can only be implemented efficiently using them. Zcash uses pairings to implement a zero-knowledge protocol; TPM chips use pairings to implement Direct Anonymous Attestation; for example.