Authenticated encryption without padding I want to encrypt data and protect its integrity and confidentiality. However, I cannot increase the length of the data.

Are there any cipher modes of operation which provide confidentiality and integrity protection without increasing the length of the ciphertext?

If the data to protect has no built-in redundancy at all (for example, has each of its bit determined by fair coin toss), there is no way to protect integrity without expansion (Proof sketch: there are as many distinct possibilities for valid plaintext as there as possibilities for valid enciphered-and-protected data, hence every possible enciphered-and-protected data must be acceptable by the verify-and-decipher operation).

If the data to protect has some built-in redundant part (like, a fixed header of 16 octets), then we can remove it, use normal authenticated encryption, and restore the redundancy after the verify-and-decipher step. Variant: if we are certain that some lossless compression scheme will shrink the data enough (e.g. the plaintext is 2227 symbols restricted to 246 possible values, each coded as an octet, allowing to encode that plaintext as 2211 arbitrary octets by mere conversion from base 246 to base 256, making room for 16 octets), we can compress the data before applying the authenticated encryption, and expand after the verify-and-decipher step.

If the data to protect has some built-in redundancy that we have no way to turn into compressibility but can nevertheless characterize (like, plaintext is the result of applying Bzip2 compression to about one page of sensible English text), we have the option to use Format preserving encryption (that is, in the context, a block cipher with the block size equal to the data size, that implements a key-dependent, random-like, reversible transformation of the whole data). Any alteration of the ciphertext (other than replacing it with a known-valid ciphertext) will make the whole deciphered plaintext random, and we can reliably detect that (with a Bzip2 decompression algorithm hardened against rogue input, followed by even the most basic validation that the output contains a large-enough proportion of English words). Notice however that we loose something on confidentiality: contrary to the previous solution, the same plaintext will always be enciphered to the same ciphertext, which sometime is unacceptable, and does not match the modern goals of a cipher.


Playfair cipher - questions about inserting 'X' I'm implementing the Playfair cipher as part of a programming project. I realize there are different versions of the cipher - I've been asked to implement the version which treats the letters 'I' and 'J' as the same letter, and which inserts the letter 'X' into the plaintext to ensure that every resulting bigram has unique letters ("TREESTUMP" becomes "TR EX ES TU MP"). It is also meant to append the letter 'X' if the length of the intermediate plaintext is not even ("SMOOCH" becomes "SM OX OC HX").

My first two questions have to do with the encryption process, the third has to do with the decryption process:

How are messages resolved which already end with an 'X', and have an
odd number of characters? For example, "REX" becomes "RE XX" -
surely that can't be right.
The Playfair Wikipedia article explains that 'X' is a good candidate
for insertions because it is an uncommon letter. However, it seems
to me that a cipher should be able to encrypt any message
irrespective of content - what if my plaintext contains two adjacent
'X's? For example, "REX XENOS" becomes "RE XX EN OS" - we can't be
expected to keep naively inserting 'X's between the two 'X's, no?
Finally, the Wikipedia article ends it's description of the cipher
by saying "drop[...] any extra "X"s or "Q"s that do not make sense
in the final message when finished", but it is not explained how
this is done. How can we know if an 'X' doesn't make sense in the
final message?

As Maarten notes in the comments, you're indeed expecting rather too much from an old classical cipher designed to be used by hand.  Ciphers from that era were simply not designed to be able to mechanically and unambiguously encode all possible messages.

Basically, as you've noted, the Playfair cipher as you've described it cannot encrypt all messages; specifically, it cannot handle messages where two consecutive identical letters fall into the same group, nor messages of odd length.  (There are Playfair variants that can handle both of those in various ways, but you don't seem to be using any of those variants.)

It is thus the encryptor's responsibility to somehow ensure that their message is of a suitable form to be encrypted with the cipher, while still (hopefully) conveying the appropriate meaning to the recipient when decrypted.

One common convention for doing that is to break up unencryptable plaintext segments (or pad messages with an unsuitable length) by inserting a dummy letter that is obviously misplaced, and which the recipient can therefore safely ignore while reading the message.  X and Q are common choices for such dummy letters, being rare in normal English text, but really any letter can be used.  So, for example, if you needed to break up a rare double X, you could e.g. turn it into XQX or XZX or whatever; it just needs to be something that the recipient can spot as an obvious error, and which they can be expected to be able to reliably correct.

But note that you also have other options: for example, you could simply choose to rephrase your message using different words that don't contain the problematic double letter.  Or, for the specific case of the Playfair cipher, you could simply choose to insert an extra dummy letter somewhere earlier in the message (or just adjust your word choice to change the length of the message) so that the double letter now gets split between two encrypted letter pairs.

In any case, note that the Playfair cipher (like most ciphers of its era) has a much more significant limitation: it cannot encode spaces or punctuation.  Thus, it cannot distinguish "inverse" from "in verse" or "No retreat!" from "No, retreat!".  So you will in any case have to take care when composing your messages to avoid potential misunderstandings due to run-on words and sentences.

(Some of that ambiguity can also be reduced by conventions like, say, inserting an X between words and a Q between sentences.  But such conventions are also just imperfect patches on top of a fundamentally limited encoding scheme.)

Of course, the Playfair cipher has other limitations too, like the inability to express letters outside the English alphabet.  Indeed, it cannot even represent all the letters in the English alphabet, typically conflating I and J into a single symbol.  Again, this is just something that the receiver is expected to be able to disambiguate based on context.


Why does a transcript which is indistinguishable from a fake one show zero knowledge? Is there an intuitive way to understand why having a transcript that the verifier could have created themselves and is indistinguishable from a real transcript , shows zero knowledge?

The information that the verifier gets is all contained in the real transcript. On the other hand, the verifier generates the simulated or fake transcript without interacting with the prover, so all information contained in such a fake transcript is nothing beyond the given fact that "the statement to be proved is true". Now if the real transcript is indistinguishable from the fake one for any adversary with reasonable resources, then clearly these two transcripts contain the same amount of information. Therefore, the real transcript does not leak any information beyond the given fact, i.e., it is zero-knowledge.


Are deployed MACs IND-CPA? There are a number of message authentication codes (MACs) used in practice. They are highly used in practice (f.ex. in TLS), but there's (at least) one application where they can't be used: Full Disk Encryption (FDE).

Now most FDE applications just don't bother with authentication. TrueCrypt for example has no authentication mechanism in place for authenticating the bulk data. However it uses CRC-32 (!) to ensure integrity of the data encryption keys in the header. The advantage this provides is that the ciphertext may be completely indistuingishable from random.

Now I want to create a data container format with the same property (complete file is random-looking) but want to perform strong authentication of the data encryption keys. This means I need to use authenticated encryption (AE).

Most of the AE schemes append a tag to the ciphertext and to ensure pseudorandomness of the whole file this tag also has to be random looking. The desired notion for this would be IND-CPA.

So my question:
Are the output tags of the common MACs / AE-modes indistinguishable from random data under chosen plaintext (or eavesdropper?) attacks?

What is considered common MACs / AE-modes:

GCM
EAX
CWC
HMAC
CMAC / CCM

The property you are probably looking for is whether the MACs are PRF.

With HMAC it depends on the pseudo-randomness of the hash function used. If the hash is a PRF then the HMAC is as well. However, that is not required for MAC security of HMAC, so it's not necessarily true even with a secure HMAC. See New Proofs for NMAC and HMAC: Security without Collision-Resistance.

In both of EAX and CMAC, the MAC is a particular (unique) output of the block cipher and is indistinguishable from random as long as the block cipher is a PRP and the outputs are not seen too many times to distinguish a PRP from a PRF.

Similarly, GCM outputs the XOR of a unique block cipher output with the GHASH and so is PRF as long as the block cipher is. (You also have to assume that the GHASH output is independent of the block cipher output.)

CWC has a Carter-Wegman MAC that is again indistinguishable as long the block cipher is, because it outputs a XOR of two independent block cipher outputs.


Comparing Files: Is it better to use multiple hash algorithms or just one? I'm looking to compare (for byte-for-byte equality) two binary files.

I already have the process down:

Check for existence etc.
Compare file lengths
Use a hash or CRC of a sort (right now I use MD5) to look for an obvious inequality
Finally, byte-for-byte compare them (I have a way of doing this in chunks to speed it up).

Note: the last bullet means I am fully aware of, and prepared for, collisions. I am aware that two identical hashes does not imply equality, but two different hashes confirms inequality.

Here are my thoughts on this so far:

The MD5 function I'm using just takes a file stream and gives me the results. I'm a crypto noob so I don't know much about this algorithm, but if there are random reads and writes (totalling a fraction of the file size) this would likely be much faster than reading in the whole file, or using its ComputeHash(byte[]) overload. That means it would be much faster than reading the file for the byte-for-byte comparison
On the other hand, to make a hash that's based very strongly on the file's contents so that one small change has a good chance of changing the hash, I would think it would need to read a good chunk of the file, so maybe this isn't much faster.
The point with the thoughts above is this: if the hash computations for (weak) comparison are significantly faster than the raw comparison, then it appears it would be worth using multiple different hash algorithms before the raw comparison may be necessary. But is this true?

My particular application: These are small (a few KB) binary files I have a user upload to an app we host on our network. If it's different than our network copy I want to force them to update our network before they can do things with it. However, I don't want to limit my function to this application, but learn how far it may go with others.

Now all I'm wondering is this: Is it better to use multiple hash algorithms to do such a comparison?

Bonus Points: If you think I could be using different algorithms for speed, feel free to recommend.

MD5 is vulnerable to a lot of collision attacks, so if you don't trust the users it is possible for them to make files which hash to the same value as other files but which are not in fact the same.

I think you are misunderstanding how a hash works though.  It does not read bits and pieces of the file, it processes the whole thing into a small output which is a "signature" of that file.  With very, very high probability (if your hash function is good) it is unlikely that two files will create the same hash if they are not, in fact, the same file.  But, it is not by itself any faster than comparing piecewise whether two files are equal.

Where it helps is when you have a bunch of files and you want to check whether a new file is the same as one that you already have.  You can store the individual hashes of the files, and then just check the hash of the new file against all of the existing hashes.  Now instead of manually checking file vs file over and over, you can just compare the small hash values.


How to hash a structure that needs to include that hash's outcome? so I am busy writing a TCP protocol in which I send a "packet header" with each packet of data. This packet header is a structure that contains information about the data that was sent. I want to verify whether the header was tampered with in some manner and I am thinking of using a hash of the header to ensure it was not tampered with. I want to know if it is possible to include this hash in the header itself. Here is what the packet header looks like.

struct PACKET_HEADER
{
    DWORD dwMagic;
    BYTE lpvChecksum[32];

... Rest of header follows

I am not sure if this method will work and I am open to any other suggestions on how to verify the header.

Thanks

First, a hash does not provide integrity. You would need a MAC (like HMAC) or a digital signature to ensure the message hasn't changed in transit.

You'll have to put some standard value (say all zeros) into the field which holds the MAC, compute the MAC, then insert the value. Otherwise you have a chicken and egg problem. You need the MAC value to compute the MAC value. So which comes first the MAC or the header you want to compute the MAC over. See the issue?

To verify the MAC, the receiver would pull out the MAC tag, replace it with all zeros (or whatever you used), compute what the MAC should be, compare with the extracted tag.

If you are not restricted to the header as defined, placing the buffer for the MAC at the end of the header would be the best. That way you can just MAC the data before the MAC slot.


How to do Hexadecimal multiplication in GF(2^8) I'm trying to do a hexadecimal multiplication in GF(2^8).
Now, I know the technique of shifting left the binary numbers in some cases, for example:

02 * 9E
0000 0010 * 1001 1110

you shift one time the 9E part, which results in the following:
0011 1100
and since it went above x^8, you must calculate the XOR operation with the Irreducible polynomial x^8 + x^4 + x^3 + x

and the result would be
0010 0110

I know how many spaces to shift when the first polynomial is a simple one, like
0010 or 0100, but how about when it is a little more complex?
Such as
0111 or 1011?? Hoy many spaces must i shift it?

0111 = 7, so i shift 7 times? or 2 because the greates expoent in the polynomial is 2??

Your help would be very much appreciated!

You cannot use (just) a bit shift to multiply by $7$.  Not in ${\rm GF}(2^n)$, and not in normal arithmetic either.

Shifting a number left by one bit always multiplies it by two, and shifting a number left by multiple bits is just equivalent to shifting it left by one bit several times.  So shifting a number left (by one or more bits) always multiplies it by a power of two.

To multiply a number by a factor that is not a power of two, you need both shifting and addition (which in ${\rm GF}(2^n)$ is actually bitwise XOR).  For example, $7 = 111_2 = 4 + 2 + 1$, so $7a = 4a + 2a + a$ for any $a$.  So, to multiply some number $a$ by $7$, you can first calculate $2a$ and $4a$ by shifting $a$ left, and then add those together with $a$ itself (always remembering that, in ${\rm GF}(2^n)$, addition is actually XOR and that any results with more than $n$ bits will need to be reduced modulo the field polynomial).

More generally, we can do general multiplication in ${\rm GF}(2^n)$ by splitting one of the numbers being multiplied into a sum of powers of two (which is really easy if we're working on a binary computer), use bit shifting (and modular reduction) to multiply the other number by those powers of two, and then add the results together.  Here's some pseudo-C code to illustrate this:

const int overflow = 0x100, modulus = 0x11B;  // AES GF(2^8) representation

int gf2n_multiply(int a, int b) {
    int sum = 0;
    while (b > 0) {
        if (b & 1) sum = sum ^ a;             // if last bit of b is 1, add a to the sum
        b = b >> 1;                           // divide b by 2, discarding the last bit
        a = a << 1;                           // multiply a by 2
        if (a & overflow) a = a ^ modulus;    // reduce a modulo the AES polynomial
    }
    return sum;
}

Note that you could easily turn the code above into a normal integer multiplication routine by replacing sum ^ a with sum + a and removing the last line in the while loop that reduces a modulo the AES polynomial after it has been shifted left.  Those are the only ways in which Galois field arithmetic, as used in this code, differs from normal integer arithmetic.

Also note that, while the code above should work (in the sense of producing the correct results), it's probably not something you should use in production crypto code.  Not only is it not particularly well optimized, but its running time depends on the value of b, which is generally not desirable if b might contain sensitive data that you don't want to leak.

(BTW, at this point you might be wondering if it wouldn't be more efficient, for example, to calculate $7a$ as $8a - a$ instead.  Unfortunately, while that would work fine in normal integer arithmetic, addition and subtraction in ${\rm GF}(2^n)$ work differently, and we actually have $8 - 1 = 8 + 1 = 9 \ne 7$.  But adding together distinct powers of two still works the same way in ${\rm GF}(2^n)$ as it does with normal integers, so we can still usefully work with the binary representation of numbers.)


How to hash a set of elements Imagine the following senario. We have $n$ participants. Participant $i$ has a set of elements $S_i$ with the elements being in a random order, possibly different for each participant.

The participants want some way to get something like a "hash" of the sets. Particularly they want for the hash to be collision resistant, so that it is hard to find two different sets with the same hash.

The hash function should also be pre-image attack resistant, so that given a hash (or a set) it is hard to find a (another) set that hashes to this values.

The catch is that the participants cannot reorder their sets. This means that the hash function must be order independant of the order of the elements but not of their contents.

Is there a secure and solid way to fulfil the requirements?

( I had a simple idea, to compute something like $SetHash(S) = Hash(e_1) \oplus Hash(e_2) \oplus \dots \oplus Hash(e_n)$ which i think satisfies the preimage attack resistance property but i cant formally prove that it is also collision resistant)

The basic problem seems to be that of canonicalization. If you can't reorder the set, then you will have to choose a commutative, associative, operator to concatenate the values; $a \otimes b = b \otimes a$ and also $a \otimes (b \otimes c) = (a \otimes b) \otimes c$

An immediate candidate for this would be to interpret the elements, $m_i$ as integers and let $\otimes$ be integer multiplication. You could then pass it through a secure hash function $H(\prod m_i)$ to get your final hash.

To improve the collision resistance with this choice of $\otimes$ operation (unfortunately $H(5 \times 4) = H(10 \times 2)$; different sets with the same hash) you might consider associating each message with a unique prime number, and by the fundamental theorem of arithmetic, this product will be unique.


How to pronounce RIPEMD 160? Do I pronounce it as a word or do I make it sound like "R-I-P-E-M-D" like by pronouncing each individual letter.

It is pronounced RIPE "tiny pause" M-D (RIPE for RACE Integrity Primitives Evaluation and M-D for message digest).


Is 80 bits of key size considered safe against brute force attacks? I came across the KATAN family of ciphers for small domain input blocks. They cipher arbitrary block lengths: 32, 48 and 64, but their key size is 80 bits only.

Is 80 bits of key size considered safe against brute force attacks with current state of the art processors?

TL;DR: no longer unconditionally.
As of 16 Feb 2021, the Bitcoin miners hashed at an aggregate rate of $\approx154 \cdot10^{18}H/s$ according to this source, where one hash is two nested SHA-256; that is $\approx2^{93.0}$ SHA-256 per year.
Here is this data redrawn in SHA-256 per year with a $\log_2$ vertical scale, to facilitate comparison with key size in bits. I believe the notable growth in 2010-2011 was the rise of GPUs, while the 2013-2014 period corresponds to an increased use of ASICs. Nowadays, bitcoin mining is mostly performed using highly specialized ASICs. Recent hardware advertises 220 T SHA-256/s at 15 pJ/SHA-256 (3250 W power on wall) for \$3769. It's sold out, and the planet struggles with carbon emissions.

Thus 80 bit of security can not blindly be said good enough today. 80-bit may be very safe, or clearly not enough, depending on a variety of factors;

Value of the target
Time frame during which a break makes sense
How easier (or harder) it is to check a key compared to SHA-256, due to

use of entropy stretching,
the amount of memory necessary per search engine

Possibility of multi-target attacks, where the attacker's goal is to find any one in several target keys, and they manage to make the cost of testing a candidate key against all target keys mostly independent of their number. That's sometime straightforward (e.g. when a ciphertext block for the same known plaintext block is available block-enciphered under all the target keys).

Addition: I second everything in Thomas Pornin's answer (Feb. 2014), except perhaps "Right now, 80 bits still seem quite sturdy" which is only valid in some contexts, including the context of the question, at least at the time.
In the context intended for KATAN (really low-end devices such as RFID tags), an expectable consequence of key recovery is to be able to clone one single RFID tag. Recovering the key is likely feasible at far lower cost than brute force, by side channel attack or micro-probing, regardless of key size (even though testing a KATAN key requires significantly less work than performing one SHA-256). So right now (Nov. 2015), 80 bits of key is not a major weakness for an individual RFID tag key on rational economic grounds (if we discount the irrationally devastating effect of the announce of any break, and the more rational desire to not have to argue on key size if such break occurs). 80 bits would not be enough for the master key from which the RFID tag keys are derived, or some other uses of KATAN.


How do I choose blind sizes? I am currently developing a service that calculates statistics (currently only sum/average) on homomorphically encrypted user data, and then gives the results to a third party. Because encryption is computationally expensive, and user devices are routers or small SoCs, I want to blind the data (e.g. add a random big number to the data value), use a blind for multiple data values, and encrypt only the blind.

Now the question is, how big does this blind have to be compared to the actual data so that it can be considered secure? For example, if I have temperature values between -20°C and +40°C, how big would I have to choose the blinds? If I take extremely big blinds, I will run into the issue of overflows, which will probably be hard to deal with, since I am summing up encrypted numbers.

You can try to encrypt your sensitive data with a lightweight cipher, like Prince. You encrypt your Prince key with a HE encryption scheme like BGV (HElib implements it) and give the cloud two things: Enc_HE(Key_Prince), Enc_PRINCE(Data). The cloud is able to decrypt homomorphically Enc_PRINCE(Data) using Enc_HE(Key_Prince) and obtain only Enc_HE(Data). The cloud can now perform unlimited computations on encrypted data. Your Key_Prince will not be found. You can find more about this scenario in: Toward Practical Homomorphic Evaluation of Block Ciphers Using Prince and Homomorphic Evaluation of the AES Circuit. HElib can be hard to use, do you might instead try a more friendly library, SEAL. But if you want to do only additions or only multiplications, there are more practicals schemes than fully homomorphic ones.


Energy consumption by mobile or sensor node when executing xor / encryption / decryption I try to estimate the energy consumption by a sensor node when executing an authentication algorithm witch contains operations (hashing, XOR, Encryption / decryption by public/private key, addition,...).

The algorithm is named MDA (Message Digest Based Authentication). It contains:

(SN:sensor node; CH: cluster head; Th: hash operation ; Tx: transmit;
 Touex: XOR; Trec: reception; Tenc: encryption; Tdec: decryption)
**-Registration Phase :**
*SN-->CH:
2Th+Tx+Touex
*CH-->SN:
Trec+Touex+3Th+Tenc+Tx
**- Authentication Phase :**
*SN-->Ch
Th+2Tenc+Tx
*CH-->SN
Trec+Touex+2Tdec+Th
**- Numeric Certif**
*CH-->SN
Th+Tenc+Tx
*SN:
Trec+Tdec

So I ask if there are measurements that I can use to calculate energy.

There's a degree of electronics twiddling necessary for this.  You start with:-

A stiff power supply passing through a shunt resistor is typically used, which is then monitored with a storage oscilloscope. A low resistance is necessary, say 0.1 Ohms, but that really depends on the operating point consumption of your sensor device. You can't have the power supply dipping below operational thresholds as that will nullify the experiment.  Control the device to perform your required operations, and you'll read a voltage off the scope.  Then simply $consumption = \frac{voltage}{resistance}$.

This is called power analysis, and Wiki has an entry level article. You'll see from the graphic on the RHS that the power signature is not really as simple as I implied.  That's where a lot of statistics and probability matching will become necessary.  Some don't even bother with power consumption (amps) calculations and go with purely graphical approaches.  A wibbly waveform might indicate a correct key, and a wobbly waveform might indicate a bad key. This part is entirely characteristic of the individual device under test. And how you intend to exactly distinguish various cryptographic operations within the sensors.

Also one of the challenges will be in managing to grab and isolate the power consumption at the point of cryptographic operation, rather than simply running the status LEDs. You may need additional wiring between the control inputs and the oscilloscope's trigger input.

But it's a start...


Why do I want to use PGP subkeys? I understand the general notion in play: if my laptop/computer is stolen or compromised I can revoke that particular subkey so (as long as people have updated their keys) they can't impersonate me. However, the compromiser can still read messages intended for me as far as I understand. So, maybe I don't lose signatures but if the thief has a way of intercepting messages intended for me (and if they have my laptop they very well might), they would be able to read them. Am I misunderstanding or is the creation of subkeys lest beneficial than some make it out to be?

The usage of subkeys separates the collection of trust signatures from the key's usage. Trust signatures for the Web of Trust are created for you master key. This trust is inherited by your subkeys which are the ones used in the actual cryptographic operations (signing/decrypting). This has a few advantages:

Key rollover: You can use short lived subkeys (usually 1 year) which can be updated regularily without you losing the trust signatures collected.
Key compromise: As you stated, the master key should be stored offline to mitigate the consequences of a key compromise. If your subkeys are compromised, they can easily be revoked and replaced. Past communications will be left vulnerable but not future ones.


Argon2 parameters concurrent access I am trying to figure out the best parameters for Argon2 for password hashing.

I have read the RFC and the recommendations they put into it. So I follow up on the recommendation on the paper depending on my target machine.

The thing is that one single call fits perfectly into the desired time. However, they never mention several calls at the same time.

For example. I have a server with 8 CPU cores and 32GB RAM.
Then I configure an Argon2id with: 16 lanes, 1 iteration, and 128MiB memory.

I call it once. Perfect! I got an execution time of ˜50ms.
Now I simulate several calls at the same time. Execution time increases a lot. For 20 parallel calls, execution time goes up to ˜500ms.

I can tune the algorithm to fit with the average traffic on the server to fit the desired time, but every time I will have a peak, performances will be deteriorated. And this also means lowering the values which means cheaper to attack.

Which is the best way to proceed?

Even relatively modest values for the memory and time parameters will make it very hard for an attacker to do an offline brute-force attack on your users' passwords, since they have to try so many passwords to find one.
So you should pick values that allow your servers to perform acceptably, even given the maximum rate of login attempts that you permit. Denial-of-service (DOS) attacks are a risk, so you need to use appropriate methods to limit the number of simultaneous login attempts, and throttle repeated attempts before they overwhelm your memory and CPU.
See advice on
Blocking Brute Force Attacks | OWASP via CAPCHAS, secondary delays, device cookies, unpredictable behavior, lockouts by IP address, etc. See also more generic advice on defending against Denial of Service.


Use cases for CMAC vs. HMAC? Both can be used to verify the integrity of a message. Assuming you have the needed primitives available to you (i.e. the code space of needing both a cipher and a hash function isn't prohibitive), is there any reason to prefer one over an other? In practice HMAC seems to be much more widely used, is that a result of cryptographic, or social reasons?

HMAC was there first (the RFC 2104 is from 1997, while CMAC is from 2006), which is reason enough to explain its primacy. If you use HMAC, you will more easily find test vectors and implementations against which to test, and with which to interoperate, which again explains continued primacy. Being the de facto standard is a very strong position.

On many embedded systems, one may expect HMAC to be faster than CMAC, because hash functions are usually faster than block ciphers. This is not true if the platform includes some hardware optimization for a specific block cipher (e.g. dedicated AES opcodes), or if the messages are short (HMAC has the same asymptotic cost as hashing, but also a fixed overhead), or if you do something stupid like selecting a slow hash function as a basis for HMAC (e.g. Whirlpool). As with all performance things, actual measures are needed to reach any kind of definitive conclusion.

If you need to both encrypt and MAC, then the smart thing to do is not HMAC or CMAC, but rather to use an authenticated encryption mode which will do both properly, simultaneously, and at a lower cost (or at least so it is hoped). Usual candidates are EAX and GCM. The CAESAR competition was held to find new, better AE (Authenticated Encryption) ciphers.


Doubling the block length of a given block cipher IMHO the main essence of a Feistel cipher of block length $n$ is the working of a non-linear function $F$ that is applied to the two halves of the block of length $n/2$.

Now suppose a certain block cipher of block length $n$ as well as two keys of it are given. If one employs the given block cipher in the sense of $F$ on each half of a larger block of length $2n$ in parallel (actually invoked alternatingly with the two keys) for a number of rounds, one obtains evidently a new block cipher of Feistel genre having doubled block length and requiring a doubled key length.

Could anything in general be said on the security (or insecurity) of such a scheme?

It may be of interest to also examine the special case where the two keys are identical.

The scheme can be trivially generalized to achieve a block length of the larger cipher of $m \times n$ where $m \geq 2$ operating on $m$ subblocks of length $n$ as follows, with $E(K,P)$ denoting the given block cipher and $K[*]$ denoting the array of the keys:

for i in [1 .. number_of_rounds] do

    for j in [1 .. m] do

        subblock[j+1 mod m] ^= E(K[j],subblock[j])

Note that, in case $m$ is not fixed but the plaintext length is $m \times n$ (and there is one or more keys) one obtains a special kind of block chaining with the given block cipher.

Certainly there is an efficiency issue that needs to be examined for practical applications of the scheme.

Parallel construction

Then my first feeling is that you wouldn't lose that much in security however there are several drawbacks.

you would be basically having a kind of ECB inside your $2n$-block-cipher.
you do not have a full diffusion on your $2n$-block-cipher : if you change a bit in the first part, only that part is modified (orange diffusion on red).

$2n$-Feistel construction

However if you meant to use that $n$-block-cipher as $F$ in your Feistel $2n$-block-cipher, then you will have to make a sufficient number of rounds (at least 4 to get full diffusion : see p. 41). Therefore compared to a parallel CTR encryption method just using that $n$-block-cipher, you are 4 times slower and you don't really have a gain in security in term of key as the space is the same.

Your idea is this : given a $n$-bit block cipher, one can construct a $2n$ bit block cipher using a Feistel construction. More over you want to use 2 keys in order to increase the security margin.

Given enough rounds (at least 4), I can't see any security hole in that construction (but I'm not a cryptographer yet).

$m$-blocks Feistel construction ($m \times n$ bits-block-cipher)

for i in [1 .. number_of_rounds] do
    for j in [1 .. m] do
        subblock[j+1 mod m] ^= E(K[j],subblock[j])

This construction can be displayed as such (e.g. with 5 blocks, 2 rounds)

In order to get a full diffusion you need a strict minimum of 2 rounds.
However this is the same as using the $n$-cipher as a keyed $S-box$. By the way, the more blocks you add, the closer you are to a SPN.


Is the private key static or variable key in the elgamal algorithm? I read about elgamal algorithm it work like the follow steps

Bashir chooses a large random prime p and a primitive root α modulo p.
Bashir then chooses a random integer a with 2 ≤ a < p - 1 and computes α^a  mod p.
Bashir’s public key is (p,α,α^a) and his private session key is a.

Enciphering stage consists of the following steps:

Amina obtains Bashir’s public key (p,α,α^a).
She chooses a random natural number b < p - 1.
She computes α^b  mod p and mα^ab  mod p.
Amina then sends the cipher text c = (α^b,mα^ab) to Bashir.

Deciphering stage consists of the following steps:

Bashir uses his private key to compute (α^b )^(-a)  mod p.

Then he deciphers m by computing (α^b )^(-a)  .mα^ab  mod p.
I understood this algorithm but I have Wondered simple

Imagine that we have a message consists of four parts (block data) and want Amina encrypted and sent to Bashir.
Is Amina used the same Private Key (b) Of four parts or generate a new private key for each part of the message During the session encryption.

I never thought Alice and Bob would get international counterparts. Anyway, in reading your question I've spotted some issues.

Bashir generates a public and a private key. The private key you call a private session key, which is a bit confusing and may lead to errors like the one below.
In order for Amina to encrypt something for Bashir, she has to use Bashir's public key and also generate another value, (b), which is called the ephemeral key  or session key, hence the confusion I mention above.

To answer your question: Amina has to generate a new ephemeral key (b) for each message. If she uses the same key for all messages, and two messages happen to be the same, the corresponding ciphertexts will be the same as well. Moreover if someone gets his hands  on a plaintext, he can figure out the ephemeral key and seriously compromise all the messages encrypted with the same ephemeral key. Therefore Amina must generate a new ephemeral key every time.


Potential vulnerability in DH key selection - am I understanding this right? I'm reading through a DH implementation, and I think I found a potential hole.

Public $p$ and $g$ values are properly selected.
A candidate secret value $\bar a$ is pseudo-randomly selected such that $0 \leq \bar a < 2^{|p|}$, where $|p|$ is the number of bits required to store $p$.
If $\bar a \geq p$, discard it and repeat the previous step. Otherwise select it as the secret value $a$.

This already leaks some information about the output of the PRNG, since measuring the number of repeated selections via timing tells us how many $\bar a$ values were chosen such that $\bar a \geq p$. Whilst the PRNG is poor (it's Java's inbuilt Random class), this doesn't constitute a feasible timing attack.

An interesting case is when $p$ is close to $2^{|p|}$, since there will be cases where the $\bar a \geq p$ condition will only be met when certain bits are set. For example:

$p = 0xFE4041FB$, or 11111110010000000100000111111011 in binary.
$|p| = 32$, therefore the maximum selected $\bar a$ value will be $2^{|p|}-1 = 0xFFFFFFFF$.
For every iteration in the loop, we know that $\bar a \geq p$, so the first 7 bits of $\bar a$ must have been 1.

Am I correct here, or have I missed something? Are there any other holes?

If an implementation uses a poor PRNG, there will always be vulnerabilities in that implementation. However, if you replace Random for a cryptographically secure PRNG, the method you describe for generating private exponents is fine. In such case the timings will only reveal information about:

The public modulus $p$, which may be presumed to be known already, and
The discarded values.

A CSPRNG will output values that are indistinguishable from uniform and therefore computationally unrelated. Hence, learning information about the values that are discarded, will not reveal any information about the value that is eventually selected.


Why is only one generator stated in literature for elliptic curve group P-256? I refer to elliptic curve groups over prime fields and their application in cryptography.

If the order of a group is prime, it follows (am I wrong?) that:

the group is cyclic and
every element beside the zero element is a generator.

To my knowledge the first statement is well known and last statement is a consequence of the theorem:

If G is a cyclic group of order n and $\phi$ is Euler'sPhi-Function, then G has exactly $\phi(n)$ generators.

Now, if n=p is prime, then $\phi(p) = p-1$.
Therefore it follows (2).

But: The order of P-256 (n=115792089210356248762697446949407573529996955224135760342422259061068512044369) is prime. So every point in this group beside the point at infinity should be a generater of the whole group. Why is a particular base point given in all the literature:

$G=(x,y)$, with

x=048439561293906451759052585252797914202762949526041747995844080717082404635286
y=002258390684796862237411570494974242622288194167061563441992324890848025900319

when every point is an equally good possible base point? is it just a convention to use that particular point and for what reason?

You are correct.
All points in a prime order curve (except $\infty$) are generators of the whole group.

But for practical applications a specific one must be chosen to make protocols work.

For example, Diffie-Hellman works only if the two public keys are computed as a random multiple of the same generator.

So it make sense that, among the curve's parameters, there is also a chosen, fixed, base point.

You are free to design protocols with alternative generators, but, as any point (except $\infty$) is as good, it makes no sense for interoperability purposes.

For P-256 the choice of the generator, like for the curve's parameter $b$, is done using a deterministic algorithm with a (supposedly) random input seed.

Other curves might have different way of choosing it. For example curve25519 uses the point with the lowest absolute value of $x$ belonging to the large prime order subgroup.


Are ZKPPs possible with server-side hashed passwords? A basic ZKPP (Zero Knowledge Password Proof) is based on the server being able to challenge the client, and the client can then prove it knows the password (in such a way that is verifiable to the server) without transmitting the password itself.

However, in order for the server to issue the challenge and verify the response, it seems like the server would need to have the password in plaintext. Anybody gaining access to the server would be able to simply retrieve the password.

Is it possible to create a ZKPP such that the server only maintains a hashed version of the password, and yet is still able to issue the challenge and verification?

Short answer: YES. (Though see the note on "hashed" below.)

Intro

The remote authentication protocols where server does not know the plaintext password are generally known as augmented password authenticated key agreement (PAKE). You can see this wikipedia article for details of PAKE algorithms (augmented and non-augmented). You may find this reference useful to find out more about the common protocols.

Not hash

Usual symmetric key cryptography is not sufficient for creating augmented PAKE mechanisms. Therefore,  in augmented PAKE mechanisms (as far as I know them) it is not sufficient for the server to store hash of password. They mechanisms are based on operations commonly used in public-key cryptography (such as Finite Field Cryptography) and thus, the material stored by server is commonly something akin to a public key instead of hash. (Functionally this can be considered to be similar, but the storage space consumed per user is more than traditional password hashes require.)

The augmented PAKE ZKPP algorithms include e.g. SPEKE, Augmented-EKE, and SRP.


How to compute the dot product on encrypted values? Is there a practical homomorphic encryption scheme that can give reasonable execution time results in computing a dot product:
$$a_1*b_1 + a_2*b_2 +a_3*b_3 +\ldots+ a_n*b_n$$
I imagine the scheme will need to support additions and multiplications to achieve this, so I assume we will need something that is fully homomorphic.  Is there any scheme that can do this efficiently?

Yes, there is a solution.  Ricky Demer pointed to it.  (Thank you, Ricky!)

In particular, the following paper provides an elegant and efficient solution to your problem:

Evaluating 2-DNF Formulas on Ciphertexts, Dan Boneh, Eu-Jin Goh, Kobbi Nissim, TCC 2005.

They show how to build a public-key encryption algorithm $E(\cdot)$ with the following two useful properties:

Additively homomorphic. Given $E(x)$ and $E(y)$, anyone can compute $E(x+y)$.
Can multiply (once). Given $E(x)$ and $E(y)$ (neither of which was generated as a result of a multiplication operation), anyone can compute $E(x \cdot y)$.  You can use the result in addition operations, but you cannot use it in any multiplication operations (the result of a multiplication is tainted, and tainted values cannot be used as the input to another multiplication).

This is enough to let you compute the inner product.

Here how this is helpful.  Suppose you are given encryptions of $a_1,\dots,a_n,b_1,\dots,b_n$, where each ciphertext was encrypted using the scheme mentioned above.  So, you have $E(a_1),\dots,E(a_n),E(b_1),\dots,E(b_n)$.  By using the "multiply (once)" scheme, you can compute $E(a_1 b_1), \dots, E(a_n b_n)$, i.e., an encryption of $a_i * b_i$ for each $i$.  Now you can use the "additively homomorphic" property to compute the sum of these, i.e., to compute $E(a_1 b_1 + \dots + a_n b_n)$.  This is an encryption of the inner product, as you requested.

In short: given encryptions of the $a_i,b_i$ values, you can compute an encryption of the inner product, using the above scheme.  This solves your problem.  The encryption algorithm is pretty efficient (vastly more efficient than fully homomorphic cryptography).  Incidentally, you don't need fully homomorphic encryption to solve your problem, which means that you should be able to obtain a much more efficient solution (using the above scheme) than if you tried to use fully homomorphic crypto.


RSA PKCS#1 OAEP Padding Schema - padding 0 for first octet? In this document, it shows the EM will have one zero octet padding prefixed.
                     +----------+---------+-------+
                DB = |  lHash   |    PS   |   M   |
                     +----------+---------+-------+
                                    |
          +----------+              V
          |   seed   |--> MGF ---> xor
          +----------+              |
                |                   |
       +--+     V                   |
       |00|    xor <----- MGF <-----|
       +--+     |                   |
         |      |                   |
         V      V                   V
       +--+----------+----------------------------+
 EM =  |00|maskedSeed|          maskedDB          |
       +--+----------+----------------------------+

However, in this document, page 37, it does not have this 00 octet.
For the standard (or the implementation of openssl) RSA PKCS#1 OAEP padding, which one (with 00 octet or without octet) is the standard/correct?
In fact, I've done the following tests:

I use RSA_public_encrypt(RSA_PKCS1_OAEP_PADDING) and find out the
max message length is 214, which should be yielded by 256-20*2-2(k - 2hLen - 2).However, per https://www.openssl.org/docs/man1.0.2/man3/RSA_private_decrypt.html, it mentions "EME-OAEP as defined in PKCS #1 v2.0" so I think it should be based on rfc2437. But the max length for rfc2437 is "emLen-1-2hLen", which is a conflict?

I use RSA_public_encrypt(RSA_PKCS1_OAEP_PADDING) to encrypt a
message(8 bytes only) and then use
RSA_public_decrypt(RSA_NO_PADDING) to decrypt it to see the output. I notice there always be a leading 00 octet padded. This suggests it is based on rfc3447(v2.1). I also have no idea about this.

According to RFC 2437...

RSAES-OAEP can operate on messages of length up to $k-2-2\cdot hLen$ octets, where $hLen$ is the length of the hash function output for EME-OAEP and $k$ is the length in octets of the recipient's RSA modulus.
The padding string $\text{PS}$ in EME-PKCS1-v1_5 is at least eight octets long, which is a security condition for public-key operations that prevents an attacker from recovering data by trying all possible encryption blocks.

Generate an octet string PS consisting of $emLen-||M||-2\cdot hLen-1$ zero octets. The length of $\text{PS}$ may be $0$.

concisely,  the length of zero padding will be $${emLen-||M||-2\cdot hLen-1}$$

Running with OpenSSL;
openssl rsautl -decrypt -inkey priv2.txt -in cipher.txt  -raw -hexdump
and the first line of the output is;
0000 - 00 25 2b 2c e4 b5 a8 6c-a1 d1 cc bd 0b 26 d2 9c   .%+,...l.....&..
You can see that the first byte above is 0x00


Pollard's Kangaroo-- What is the failure probability (assuming random functions)? I'm reading Pollard's paper on solving the discrete log problem, i.e. to find $x$ given $y = g^x$, where $g$ is a generator of the group.

He has a Kangaroo Algorithm (page 4) which allows you, if you know that $x$ is in a range of size $w$, to find $x$ in time $O (\sqrt{w})$ and constant space. Very cool. This algorithm is also well described on the Wikipedia page.

There doesn't seem to be a complete analysis of the failure probability, though. For instance, if the size of the set, $|S|=1$, then each hop will be of the same length, and so the "wild kangaroo" has a pretty good chance of escaping all the traps. So it seems that the size of the set should affect the failure probability, but this parameter does not seem to appear in any of the analysis (except maybe in some examples on page 6).

Is there a good analysis of the failure probability of this protocol? Also what set $S$ is good in practice? Pollard suggests powers of 2 but this is based on a fairly small set of possible $S$ he looked at--has any analysis since Pollard's original paper confirmed that this is a good choice of $S$?

Edlyn Teske has had a look at this question in her paper, specifically in section 6.3. I restate it in your notation:

  Kangaroos running in cycles During a kangaroo's travel, there is a possibility that the sequence of its spots beomes periodic. While cycles are the ultimate goals in the rho method, they
  do not reveal any information about $x$ (the discrete log) in the kangaroo method. [..] They don't find new distinguished points, they slow down the algorithm and even might cause it to fail.

  We show that if $w\leq  order(g)/4$, this is very unlikely to happen. As before, we first assume that
  we have only one tame and one wild kangaroo and that we work with jump distances of mean value $\beta=\sqrt{w}/2.$

She is looking at parallelization, but the above is for the non-parallel method. She then proves that the probability $\mathbb{P}$ that a kangaroo ends up in a cycle before a useful collision has occured is upper bounded by
$$
\mathbb{P}\leq \exp(-(4n/w)-2),
$$
where $n$ is the order of $g,$ in the discrete log problem $h=g^x$ under consideration.

Furthermore, Teske remarks that assuming uniformity of DL values, this bound can be tightened.


RSA Blind Signature Attack In Information Security Class I learned a non-adaptive chosen ciphertext attack using "blinding" but I just can't follow the proof and therefore can't reconstruct it. From what I've found out, it seems to be based on this Wikipedia entry (although not entirely I think): http://en.wikipedia.org/wiki/Blind_signature#Dangers_of_blind_signing

The idea is that an attacker intercepts a ciphertext, replaces it with a blinded ciphertext, and sends it to the recipient. Upon decrypting, the recipient complains because the message is corrupt and returns the decrypted, corrupt "plaintext". So far, so good. Now, if the attacker intercepts the corrupt plaintext, he is supposed to be able to decrypt it to obtain the original message.

Assuming that the corrupt message $m'$, the encryption keys $c$ and $n$ (where $n$ = $p$ * $q$) are public, and $d$ is the recipients' private decryption key, the proof is supposed to be:

 $$1) \ m' = (m^c * z^c )^d\ mod\ n = m^{c*d} * z^{c*d} \ mod\ n $$
$$ 2)\  c*d\ mod\ n = 1$$
$$ 3)\ m' = m^1 * z^1 mod\ n\ \ \ \ \ (edit:\ because\ of\ 2)$$
$$ 4)\ m = z^{-1} * m' $$

I understand that the attacker can intercept the corrupt message $m'$ in step 1). What I don't understand is step 2). Shouldn't it be $c*d\ mod\ \phi(n) = 1$, where $\phi$ is Euler's totient function? After all $d$, which is the multiplicative inverse of $c$, is calculated $mod\ \phi(n)$, which only the recipient can calculate because he has $p$ and $q$.

You are correct; whoever put together the above proof typo'ed that point; we have $c \times d \equiv 1 \pmod {\phi(n)}$, or more accurately, $c \times d \equiv 1 \pmod {lcm(p-1, q-1)}$.

On the other hand, the attacker isn't expected to be able to compute step 2 (he can't, he doesn't know the value of $lcm(p-1,q-1)$, and hence cannot compute $d$).  Instead, it is there to establish the relationship between $c$ and $d$ (and why they cancel out in step 3)


How long does it take a quantum computer to brute force AES? I understand that using Grover's algorithm it only requires $2^{64}$ lookups for a 128 bit AES encryption, leading people to say we need to increase to 256 bit keys. But how long would it actually take a quantum computer to do $2^{64}$ lookups?

I can't say I fully understand quantum computers, but aren't people making the assumption that 128 bit is only unsafe to quantum computers because 64 bit (which 128 bit becomes using a quantum computer) can be broken through brute force on our current computers...? Even if a quantum computer only needs to do $2^{64}$ lookups, presumably it doesn't do them at the exact speed of current computers.

When people have asked in the past how long a quantum computer would take to break AES 128 bit, people always answer that it would take $2^{64}$ lookups (which some people take to mean the amount of time we currently take to break 64 bit), but there's never any indication of an actual time.

I understand that quantum computers are highly theoretical at this stage in terms of large scale implementation, but can anyone offer any ideas?

I'm not going to exactly answer your question, because I have no idea. I simply do not know how fast the quantum computer is that NSA is building in secret.

However I could explain why people recommend 256-bit security in the face of quantum computing using some numbers. If you feel that $2^{128}$ is a comfortable security against bruteforcing, remember that a $2^{64}$ security level is $18446744073709551616$ times faster to bruteforce.

That means a ~0.000000000162630 GHz quantum processor bruteforces a 128 bit key faster than a 3GHz regular processor, assuming one lookup per cycle.


Is there an oblivious decryption scheme? Alice has $K$;
Bob has $E(K, m)$;

Is there such a scheme that enables Alice decrypts $E(K, m)$ without knowing $m$, and Bob gets $m$ ?

Yes.

The easiest way is if $K$ is an RSA private key, and Bob has the public key.

Then, here's how it works; we'll call the ciphertext that Bob has $C$:

Bob selects a random number $r$, and computes both $C \cdot r^e \bmod N$ and $r^{-1} \bmod N$ (where $e$ and $N$ are the public exponent and the modulus from the public key)
Bob sends $C \cdot r^e \bmod N$ to Alice
Alice uses her private key to compute $(C \cdot r^e)^d = C^d \cdot r \pmod{n}$, and sends that back to Bob
Bob then computes $(C^d \cdot r) \cdot r^{-1} = C^d \pmod{n}$; that is the decrypted message (and Bob can then remove the RSA padding).

Alice learns nothing, because since $r$ is a random number, so is $r^e$, and so the value she sees is uncorrelated to the original message.  Bob learns the decryption, but he doesn't learn anything else.

Now, it is possible to do this with any encryption algorithm (using secure circuits), however it is a lot more work.


How to solve Columnar Transposition Cipher without a key I have been given a 77 character message for decryption, but no matter where I look all the Columnar Transposition scripts out there are all requiring of a key. I believe the number of columns to be 7, but I am looking for a code that output all permutations of those 7 columns so that I can use a dictionary attack to find the messages that have readable words in them and reduce the number of outputs to look through.

I wrote an answer to a related question earlier showing an example of how to break a columnar transposition cipher by hand.  The basic steps are two-fold:

Test different key lengths, and look for a length where the letters in each column look like they might plausibly be consecutive.
Once you've picked a key length, shuffle the columns around until they start to line up into meaningful fragments of text.

In the linked example, these steps are made easier by knowing a distinctive word that appears in the plaintext, and specifically the fact that the ciphertext contains a single Q and a single U, which are almost guaranteed to be consecutive in English text, but the same general method can be used even in the absence of such clues.

It would probably be possible to automate this process using a stochastic optimization algorithm like randomized hill climbing: basically, pick a random initial ordering for the columns, calculate how similar the resulting plaintext looks to English (using $n$-gram frequency statistics), and then repeatedly try to move one or move consecutive columns around and see whether this makes the plaintext look more like English.  If it does, make the change and keep trying to improve it further; if not, reject the change and repeat.

For 7 columns, just trying all the 7! = 5040 possible column orders would also be feasible for a computer, although the number grows rapidly as the number of columns increases.  As noted, generating all possible permutations of the columns is a standard computations problem, for which several well known algorithms exist.


How to construct a "toy" version of Gimli permutation for three (instead of twelve) 32-bit words? I am interested to see a "toy" version of the Gimli permutation for three (instead of twelve) 32-bit words. I see that the "core" sub-permutation of Gimli operates on three 32-bit words, but I don't know how to use it for constructing a 96-bit unkeyed permutation. Is it possible to modify the Gimli algorithm to devise such a function? If yes, how?

According to the spec, the Gimli state consists of four columns of three rows of 32-bit words, for a total of 4 × 3 × 32 = 4 × 96 = 384 bits.  Each Gimli round consist of:

a non-linear SP-box applied to each 96-bit column individually,
on every second round, a linear mixing step that just swaps the first words of pairs of columns, and
on every fourth round, a constant addition step that XORs the first word of the first column with a 32-bit round constant.

Probably the simplest way to reduce the Gimli permutation to 96 bits would therefore be to simply drop all but the first 96-bit column and omit the linear mixing step entirely, as it's the only part of Gimli that actually mixes the columns together.  This will naturally give a 96-bit permutation that should resemble the full Gimli permutation in most respects, other than having a smaller state size.


Why does PGP still use the Fermat primality test? What if it hits one of the Carmichael numbers？ Since the Fermat primality test is not very reliable, most applications use it for pretesting only. Wikipedia says that PGP still uses it:

Another well known program that relies only on the Fermat test is PGP where it is only used for testing of self-generated large random values (an open source counterpart, GNU Privacy Guard, uses a Fermat pretest followed by Miller–Rabin tests).

I do not understand why PGP still uses it without being followed by the Miller–Rabin test. What if it hits Carmichael numbers?

It is a choice of the designers of PGP to stick to Fermat test. There are some nice talk since 1994

sci.crypt: 1994 - Why Fermat test for PGP primes

Critique of PGP Key Generation

and PGP Attack FAQ: The asymmetric cipher

The quote from the last;

The Carmichael Numbers
Unfortunately, there are some numbers which are not prime and which do satisfy the equation $b^{n-1} \bmod n$. These integers are known as the Carmichael Numbers, and they are quite rare. The reason for this is that a Carmichael Number must not be divisable by the square of any prime and must be the product of at least three primes). The first three Carmichael Numbers are: 561, 1105, and 1729. They are so rare, in fact, there are only 255 of them less than $10^9$. The chance of PGP generating a Carmichael Number is less than 1 in $10^{50}$.

So, even there are other alternatives to Fermat Test, they still use it.
Here the oeis/A002997 for the  Carmichael numbers;

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461

If it hits a Carmichael number then it will factor into smaller primes like $512461 =31 \cdot 61 \cdot 271$. But it can still work as a normal RSA and fool us.
Once a fast probable prime obtained then one can use proof methods instead of AKS. We may consider this as modern sieving.

1993, Atkin and Morain, Elliptic Curve and Primality Proving which can also provide a primality certificate for rapid verification which is not possible with AKS in which the number itself considered as the self-certificate for its primality.
1983,1984, Adleman–Pomerance–Rumely primality test

If you want to use the AKS then use the faster variant of AKS test. And note that AKS  is a slow and deterministic primality-proving algorithm. Here a quote from DanaJ's great answer in Math.SE Fastest way to find if a given number is prime

Anyone who suggests actually using AKS in practice has never actually run it on numbers larger than 10,000 and should be ignored.


Can two people with different one time pads securely exchange a message like this? Alice has a message, generates a one time pad, encrypts her message and sends it to Bob. Bob generates his own one time pad, encrypts the message again, and sends it back to Alice. Alice then decrypts this message using her one time pad, sends it back to Bob who then decrypts it the last time using his one time pad.

The only problems I see with this technique:

It is vulnerable to a man in the middle attack.
It requires sending the message back and forth twice between sender and recipient.
It doesn't scale well if you want to use it to communicate with multiple people.
Requires a way of generating cryptographically secure random numbers.

Does this method of encryption have a name?

If we ignore the fact that it's vulnerable to a man in the middle attack, is this method of encryption information-theoretically secure?

Why isn't this method used widely, i.e. which of the above listed problems or other problems makes this method infeasible for production use?

The general scheme is called Three-pass protocol and works for all commutative ciphers. It is secure for some of them, but xor (and modular addition) are insecure choices.

Your scheme:

A->B: $c_1 = m \oplus a$

B->A: $c_2 = c_1 \oplus b$

A->B: $c_3 = c_2 \oplus a$

B computes $m = c_3 \oplus b$

an attacker sees all of $c_1$, $c_2$ and $c_3$. So they can compute:

$c_1 \oplus c_2 \oplus c_3 = (m \oplus a) \oplus c_2 \oplus (c_2 \oplus a) = m$

and thus recovers the message.


Encryption/ciphers/codes in Chinese I am quite curious as to how you can perform simple encryption for the Chinese language.
Saw a similar question related to encryption/Chinese here: About cryptography in a character language, however the method of encryption appears to be quite complicated.
If I'm not mistaken, the method described in the answer above, requires something similar to a table which pre-maps certain characters to other characters; or the use of something like an One-time pad - both of which requires a fair amount of prior communication between both parties.
I was wondering if there is something simpler, what I have in mind is something like a Substitution cipher. That is, a way to encode the message easily, and also allowing the message to be decoded easily (if the secret key is known) or cracked given analysis or use of decoding techniques/knowledge.
For example, in English there are many ways to encrypt a message - some common/simple examples ROT13, Vigenere.
However, I can't seem to see how the concept of "pulling apart" a word can apply to Chinese characters.
For example, I can (fairly easily) encode the below using Vignere (key: chocolate), but how would I do so in Chinese?

I am learning Chinese --> K ha nslrgmpn Qjwyeli
我在學中文 --> ?

I take your question to mean, how both historically and in the modern age one could construct a pen-and-paper cipher using the Chinese language.

As pointed out in the question, Chinese is a logographic language and therefore has a far greater number of characters than Phonetic systems. Historically this has cause Chinese codes not to be based around the script.

The following claims are taken from a forum discussion and translation of ancient Chinese codes for lack of a better source.

Nüshu script may not have been intended for secrecy but it functions as such since it was almost exclusively used and readable by educated Chinese women. It was phonetic and had a set of 700 characters. This suggests that one could use the phonetic attributes of the Chinese language as a basis for a reduced character set on top of which one could implement a code.
In an earlier form of secret sharing, messages were cut into strips and delivered by different couriers.

  The so called “阴书” was to write the document vertically and cut it into 3 sections. Sent 3 persons, and each person would hold one of the sections. They would depart at different times and using different paths. When the receiver received all 3 parts, he could get the whole thing of this secret document. If one of the messengers was captured by the enemies, the enemy would have difficulties to understand the secret document. As translated by the Chinese History Forum

The technique of phrases is something I don't entirely understand I think the method is essentially to use the phonetic sound from ciphertext logographic characters to transmit a secret message. In English "eyesight hat very eight seashores create rat table" or "I ha-ve a se-cre-re-t"

  “反切” (fan3 qie4) is a kind of phonetic system originated in ancient time to help document the pronunciation of Chinese language. The basic method for (fan3 qie4) is: Take the first word 上字 (shang4 zi4 - upper word) for its starting sound (or the consonant) and the second word (xia4 zi – lower word) for its ending sound (or the vowel). The tone would follow the ending sound. Therefore, a word is separated into two parts: 声母 (sheng mu3 – starting sound), 韵母 (yun4 mu3 – ending sound). Use the 声母 sheng mu adding a 韵母yun mu from another word to form the “反切” fan qie’s first word (or upper word). Use the 声母 sheng mu from another word adding a 韵母yun mu from this word to form the “反切” fan qie’s second word (or lower word). Use the lower word’s tone for the word’s tone. The first word’s starting sound and the second word’s ending sound is the pronunciation of the original word.  As translated by the Chinese History Forum

Code sticks were used in which each stick length represented a particular pre-agreed upon the message. These stick lengths could be transmitted using signal fires without actually having to physically send the stick. More generally this technique is equivalent to code books which were also used by the ancient Chinese.

  For example, one-inch stick means victory. 9 inches stick means the army has broken the enemy army and captured the enemy generals. 8 inches stick means the enemy’s city (cities) has surrendered. 7 inches stick means successfully resisted the enemy’s army and the enemy’s army was gone. 6 inches stick means the army should be alert and defend the place diligently. As translated by the Chinese History Forum

Grille ciphers have often been remarked as excellent pen and paper ciphers for Chinese.
While I can't find any historical reference to it, transposition ciphers seem completely compatible with the Chinese language. Although one would have to choose the words carefully because some meaning would leak out as whole words are transposed rather than letters.
A method of enciphering Chinese characters similar to rot16 would be to write different characters on top of each other in different colors of ink. The key would state which color at each position was the correct character. For instance, the key could be 'blue-red-red-black-green-blue'. One of the interesting features of such a scheme is that one could design the cipher text such that all possible keys encode an apparently valid and readable message.  One advantage of this scheme would also be that it is secure against colorblind adversaries.


Proving a decision was randomly made Alice and Bob want to agree on a bit $0$ or $1$. Both know it would be fair to pick that at random, but there's no way they could meet to throw a dice and no third party they could trust. Are there known protocols that allow either side to prove that they did not manipulate the outcome?

My idea is: Both randomly (or not - but that would be in their best interest) pick $0$ or $1$, write it down, put it in an envelope and send it to the other person. Then the XOR of both bits could not have been manipulated unfairly by either party.

The problem I see with that: How can Alice prove to Bob that she did not open his envolope before making her choice?

Maybe one could instead choose an initial string $n$ and use the first $k$ with $f^k(n) < a$ as the chosen value. Now if $f$ is a cryptographic hashing function and $a$ is small Alice would have taken a long time if she were to predict $k$ before sending her own choice.

You're close with the idea of using an envelope; the standard answer is to use a commitment scheme; this is a scheme where someone can publish a 'commitment' to a value, and then later revealing what that value was.  The two essential properties of commitments are:

Someone just looking at the commitment cannot tell what the secret was
Someone with the commitment cannot reveal a value other than the value that was committed to.

How this works in this scenario is exactly analogous to your envelope method; Alice selects a random bit, and publishes a commitment to that bit.  Bob then selects a bit (there's no need for a commitment there) and publishes it; Alice then reveals the bit she committed to; the exclusive-or of Alice and Bob's bit is the output.

Now, there are a number of practical commitment schemes known.  The easiest is to use a cryptographically secure hash function; Alice selects a large random value $A$ and publishes the hash value $hash(A)$.  Bob then selects his bit and publishes it; Alice then publishes $A$ (and they use, say, the lsbit of $A$ is Alice's bit).

Looking at $hash(A)$, Bob gets no information on what the lsbit of $A$ was (assuming Alice selected a sufficiently large bit string).  This is not a formal requirement of cryptographically secure hash functions, but is a reasonable assumption with real hashes (especially if Alice chooses an $A$ which is longer than the hash function output).

And, assuming that we're using a cryptographically secure hash function, Alice cannot decide to reveal a different value $A'$; if she could, that would mean that Alice found a hash collision $hash(A) = hash(A')$, and we assume Alice can't do that.


Does Elliptic Curve Integrated Encryption Scheme (ECIES) provide IND-CCA2 security? I am looking for a faster alternative to RSA with OAEP as a IND-CCA2 public key scheme. Elliptic Curve Integrated Encryption Scheme might be a candidate, but I am not sure if it provides IND-CCA2 security.

So the question is if ECIES offers IND-CCA2 security by default? If not, what should be changed so that it does offer it?

So the question is if ECIES gives by default IND-CCA2 security?

Yes it does. There's a proof in modern Cryptography by Katz and Lindell, but I'll leave that one to Yehuda to write an answer around. This answer will instead be based on DHIES (PDF) which is the generalization of ECIES and essentially does an ephemeral DH key exchange with the public key, hashes the shared secret and performs an encrypt-then-mac authenticated encrytion of the payload using the hashed secret.

The paper states the security bound as

$$\mathrm{Adv}^{\text{ind-cca-fg}}_\text{DHIES}(t,q,\mu,c)
\leq
\mathrm{Adv}^{\text{ind-cpa-fg}}_\text{SYM}(t,0,0)+
2\cdot\mathrm{Adv}^{\text{odh}}_{\mathcal G,H}(t,q)+
2\cdot\mathrm{Adv}^{\text{suf-cma}}_\text{MAC}(t,1,c,q,\mu)$$

with $t$ being the upper bound on the time complexity of the adversary and $q$ being the upper bound on the number of decryption queries and $\mu$ being the upper bound on the number of bits asked to the decryption oracle and $c$ being an upper bound on the length of the challenge ciphertext for the CCA experiment. $\mathrm{Adv}^{\text{suf-cma}}_\text{MAC}$ is the SUF-CMA security of the MAC and $\mathrm{Adv}^{\text{ind-cpa-fg}}_\text{SYM}$ is the CPA security of the symmetric cipher.

Now only remains $\mathrm{Adv}^{\text{odh}}_{\mathcal G,H}$ which is the advantage with which an adversary can distinguish $(g^u,g^v,H(g^{uv}))$ from $(g^u,g^v,R)$ with $R,u,v$ being randomly sampled from either the group or the hash output set. Additionally the adversary is given access to an oracle computing $\mathcal H_v(X)=H(X^v)$.

So if the above Oracle Diffie-Hellman (ODH) assumption is hard for the given group (and it should be for elliptic curves), and if the symmetric cipher and the MAC are secure, then ECIES is also secure.


Finding differentials and space complexity In Differential Cryptanalysis of DES-like Cryptosystems by Biham and Shamir, they provide examples using differentials inputs such as $\Omega_p = 00\ 80\ 82\ 00\ 60\ 00\ 00\ 00_x$. Most of article is about differential cryptanalysis and presents the generic method, the way to find subkeys. But I can't find a clear explanation about how to find the differentials used in examples.
I do get the idea about feeding an S-box in order to retrieve the differentials, but these S-boxes only have 6-bit inputs for 4-bit outputs (in DES). So the memory space required in order to do such analysis is $2^6 \times 2^4 = 1024$ integers $\approx 4\ Ko$. This can be easily placed in the RAM. The method is presented in Modern Cryptanalysis (2008, Wiley Publishing; Chapter 4, pp. 122-145) by Christopher Swenson.
However, given an S-box with a bigger input such as the one used in FEAL-X (while remaining broken), we need a table of the following given size : $2^{32} \times 2^{32} = 2^{64}$ integers $\approx 2^{32}\times 16\ Go$. Such a thing is too big to store on one of today's computers.
Hence my question: how is it possible to find the right differential for bigger input round functions without the size constraint of this analysis.

If such a large Sbox with no structure were to be analysed you'd treat the analysis as a one-off precomputation.

Considering only classical differential cryptanalysis as an example, after the precomputation you'd only need to keep track of the highest probability differentials since if you combine a high probability differential with a low probability one, you've already lost quite an edge and over multiple rounds your attack will fail.

As for FEAL, there is lots of structure in the 32x32 round function and divide and conquer is the way to go.

If there was a randomly chosen huge Sbox, life would be difficult, but it is also difficult for the designer who'd have a hell of a time proving the strength of his/her randomly chosen Sbox, with any kind of guarantee. Blowfish Sboxes which are key dependent, for example, are only 8x32 (thanks @J.D.) and this helps by limiting the number of input differences that need to be considered.


Key confirmation and other benefits of double ratchet I'm trying to understand a comment from the Signal blog post Advanced cryptographic ratcheting.

This article uses the term OTR ratchet to refer to a simple asymmetric DH ratchet, where Alice contributes a new $g^{a_i}$ with every message and Bob contributes a new $g^{b_j}$. The current key is taken to be $g^{a_{i} b_{j}}$ for the maximum $i$ & $j$.

It uses the term SCIMP ratchet to refer to a simple symmetric ratchet, where the key is continuously and deterministically evolved through a KDF for each message.

Then finally the article motivates their double ratchet as a combination of the two.

My question is about the benefits of the double ratchet as articulated in this article.

The article does mention what I understand to be the main advantage: OTR ratchet itself has suboptimal forward secrecy. If Bob just sent a message, his latest DH secret key must still be in memory (since it will be used in the next DH round and combined with Alice's next DH message). Then a state compromise will allow the attacker to read the message that was just sent.

On the other hand, with the double ratchet the DH shared key is combined with the chain key. Bob's DH secret key (without the previous chain key) is not enough to decrypt the message that he just sent.

That's what I understand. What I don't understand is the insistence that OTR ratchet requires 3 rounds while the double ratchet requires 2. This is repeatedly described as an important benefit of the double ratchet. The article describes OTR ratchet as a normal 2-round DH followed by a 3rd round "acknowledgment":

  until Bob has acknowledged Alice’s next key, she can’t use it

...later:

  We wanted to incorporate a DH ratchet into our ratcheting protocol because of the “future” secrecy it provides. However, it would be nice if we could eliminate the “advertise” step in the OTR ratchet and bring it down to a “two step” ratchet. In order to achieve a “two step” ratchet, we derive a RootKey in our initial handshake KDF, and both mix it into and re-derive it from every subsequent DH KDF. This makes it possible to chain the key material together so that Alice can create and use a new DH ephemeral key immediately without first advertising it and waiting for acknowledgment.

Let's say your only goal is to avoid the key acknowledgement step. Surely you don't need to do a double ratchet -- just simply don't do key acknowledgement! Do a DH ratchet where Alice sends $g^a$, Bob sends $g^b$ and immediately encrypts something with $g^{ab}$. Why does this article say that the parties "can't" use $g^{ab}$ until Alice acknowledges? I'm willing to believe that OTR does this in practice, but I don't understand why it presents some kind of fundamental barrier. What really goes wrong if you use the key right away?

Again, I understand the double ratchet benefits of ideal forward secrecy (it can protect the message that was most recently sent, while simple DH asymmetric ratchet doesn't [and I know that performing 2 parallel DH that are out of phase by 1 round is another way achieve the same thing without a double ratchet]). But I don't understand the implication that double-ratchet is the only way / best way to allow immediate key use and do away with an extra acknowledgement round. What am I missing?

This is convenient because each new key is used one-time and depends on the root key and message, so you do not need to constantly announce the next new key and wait for confirmation.  If Bob reads the encrypted message, he knows the encryption key and can decrypt the next message.  Since by exchanging messages that need to be decrypted, you get the opportunity to know how to decrypt the next message.  This is what is called “future” encryption in the article.  Thus, we have only one root key and constantly changing ephemeral keys, which are obtained from the messages themselves.  This allows you to simply communicate while being sure that the protection is very reliable.  I recommend reading the source code for this article from 2013.  Maybe this can clarify the principle.  A potential attacker, even if he intercepts the original message and all subsequent ones, will not be able to push off from something to start the attack, because he will have messages that are always encrypted with different keys and depend on encrypted messages that need to be decrypted.


Do all files have a hash / checksum? I am curious If every single digital file has a hash  and/or a checksum. When verifying my downloaded files using hdiutil on mac os, about 90% of my files report some sort of checksum. However, when i download .iso files or ubuntu / windows, img’s or iso’s, i’ve noticed many of my image files do not report a checksum. I always assumed that if it was data, it HAS to have a checksum, or it wouldnt be data in the first place. Could someone please tell me weather or not all digital files have a checksum, and if it is possible to have files with non existent checksums? Thank you for any info!

A hash can be computed for any input, even for an empty input.

Some tools may display the output of some hash function, other tools may not.

If the file is large, it may take some time to compute, so tools may not display the hash immediately, only on-demand.

So this is more a question about specific software than cryptography.


Known Plaintext Attack for Modified OFB Mode of Operation Question: Assume a variant of the OFB mode by which we only feedback the 8 most significant bits of the cipher output. We use AES and fill the remaining 120 input bits to the cipher with 0's:

Why is this scheme weak, if we encrypt moderately large blocks of plaintexts, say 100-KByte? What is the maximum number of known plaintexts an attacker needs to completely break the scheme?
Let the feedback byte be denoted FB. Does the scheme become cryptographically stronger if we feedback the 128-bit value $FB,FB,FB,\ldots,FB$ to the input (i.e.) copy the feedback byte 16 times and use it as AES input?

Solution:

The problem with the scheme is that there are only 256 different inputs $FB_i$ to the AES algorithm. That means there are only 256 different output vectors of length 128 bit that form the keystream. To make things worse, the cipher output will run into cycle quickly. Let's denote the sequence of feedback bytes by $FB_1,FB_2,\ldots$ As soon as the feedback byte $FB_j$ is generated that is equal to an earlier one $FB_i$, i.e. $i<j$, the sequence;$$FB_i,FB_{i+1},FB{i+2},\ldots,FB_j=FB_i,FB_{i+1},\ldots$$
Repeats periodically. Since there are only 256 different values for $FB$, the maximum sequence length is 256. Since each value is associated with a 128 bit (16-byte) AES output, the keystream sequence $s_i$ has a maximum cycle length of:

128x16= 2048 byte= 2kbyte. ( Isn't that wrong? Should be 256x16 in my opinion? )

After this, the stream cipher output must repeat(and odds are that the cycle length is much shorter). Thus if an attacker has to know at most 2 kbyte of plaintext in order to recover the entire system stream cipher output with which he can decrypt all other ciphertexts.
No, we still only generate a maximum of 256 keystream words of length 16 byte.

This solution is from the manual of the book. I did not get why it is 128x 16 insteaf of 256x 16 in  part 1? Can anyone explain it to me. Also i did not get the part 2 at all. I need a comprehensive explanation.

It should be $256*128 = 4096$ bytes. The period at most 256 and each encryption outputs 128-bits.
When the $FB,FB,\ldots,FB$ series enter the plaintext, again we are taking the 8 MSB form the ciphertext that has still 256 different possibilities. To see the picture clearly;

In the first case the input space has only 256 plaintexts consist of 120-zero and the 8-bit.
In the second case the input space still has 256 plaintexts consist of repeating bytes. $$00\ldots 00, 01\ldots 01, \ldots , FF\ldots FF$$ Again, once $$FB_i = FB_j, i \neq j$$ we will have a cycle with at most 256 period.


Are there any attacks / weak points with HMAC-SHA3? I read about SHA3 and would like to study its weak point,
Are there any cryptographic attacks on SHA3-based HMAC?

No. Any such attack is yet to be discovered and would constitute a publishable result.


Bits of entropy needed to choose a random element from a list? Suppose I want to choose a random element from a list of size $2^n$, for any integer $n$. (Here, random is to mean an equal probability of selecting every item.) My intuition says I'd need $n$ bits of entropy.  For example, for a list of size 64, I'd need 6 bits of entropy.
However, how many bits of entropy would I need to choose a random element from a list that's sized something other than $2^n$?  For example, for a list of size 3, or 10?
My intuition says that I'd need to find $n$ such that $2^n$ is a multiple of list size, to ensure equal probability of selecting every item.  (This is true for all lists sized $2^n$.)  However, that doesn't seem to work in practice: there does not appear to be any $n$ such that $2^n$ that divides evenly into 3 or 10.

One can achieve this with a technique called Knuth Yao sampling. It:

Allows you to sample from any distribution $X$ of finite support (say where the function $f(i, s) = \text{the }i\text{th bit of }\Pr_X[X = s]$ is efficiently computable)
Using on average $\leq H(X) + 2$ bits of entropy, where $H(X)$ is the entropy of the distribution under consideration.

One can then replace $X$ with your distribution (say uniform on $3^n$ elements) to get the result. I'll quickly describe how Knuth-Yao sampling works for the rest of the answer.
Knuth Yao sampling works by constructing a certain (usually infinite) binary tree, and executing an unbiased random walk on it. Leaf nodes of the tree are labelled by elements on the underlying probability distribution, and when you hit a leaf node you terminate the walk and output that that element as your sample.
Why should this work?
The basic idea is to put at leaf labelled $s$ at depth $i$ iff $f(i, s) = 1$.
Then the following facts can be combined to show that the distribution of outputs of the sampler is precisely $X$:

The probability of reaching any particular node during an unbiased walk of a binary tree is $1/2^i$, where $i$ is the depth of the node
Therefore, the probability the sampler ends in a leaf labelled by $s$ at depth $i$ is $f(i, s)/2^i$ (if $f(i, s) = 0$, there are no such leaves, otherwise there is precisely 1).
The sampler can enter at most one leaf (it terminates after), so they form a set of independent events.

Then one has that:
\begin{align*}
\Pr[\text{KY sampler outputs }s]&= \sum_{i = 0}^\infty \Pr[\text{KY sampler outputs }s\text{ in depth }i]\\
&=\sum_{i = 0}^\infty f(i, s) / 2^i\\
&= \Pr[X = s]
\end{align*}
Showing that the average entropy usage is bounded by $H(X)+2$ requires a fairly careful argument, which you can find in Knuth and Yao's intial paper (which is actually quite hard to get ahold of, but can be found in one of Knuth's collections of selected papers (Selected Papers on Analysis of Algorithms, entry 34 The Complexity of Nonuniform Random Number Generation).


Questions about proof of correct encryption in the Paillier cryptosystem In the Paillier cryptosystem [1] the encryption of $m \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_n^*$ is $c = g^m r^n \bmod{n^2}$.
A proof of correct encryption could look like presented in section 4.2 of [2]:

  "Suppose a prover $P$ presents a sceptical verifier $V$ with a ciphertext $c$ and claims that it encodes plaintext $i$. A trivial way to convince $V$ would be to reveal also the random choice $r$, then $V$ can verify himself that $c = E(i, r)$. However, for use in the following, we need a solution where no extra useful information is revealed."

Although I understand the proof itself I don't get the exact point of where it is supposed to offer "extra useful information".

Comparing the proof to the proposed Zero Knowledge Proof the verifier does not learn anything apart from what the proof is all about.
$n$ and $g$ are part of the public key, $m$, $r$ and $c$ are presented for verification of encryption.
Of course the disclosure of $r$ obliterates the probabilism of the system but what is to be gained by this if you already know the plaintext?

Having asked this I have another question that seems closely related to the one above:

Supposed I were to homomorphically sum up the encryptions of a couple of messages from a limited publicly known set of plaintexts $S=\{0, 1\}$. If I then were to proof the correct encryption of the sum by disclosing the encrypted sum, the plaintext sum and the resulting random factor r for the encrypted sum - would this provide any useful information about which summand encrypts which plaintext message?

[1]
Pascal Paillier -
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
Link

[2]
Ivan Damgård and Mads Jurik -
A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System
Link

Revealing $r$ would then allow the verifier to prove to someone else (another verifier) that $c$ encodes $i$. The verifier could also prove other things knowing $r$ to a different verifier (any other proof using a paillier ciphertext, the corresponding plaintext, and the random value $r$).

With the ZKP, the verifier cannot prove anything to anyone else about that ciphertext. This seems like a useful property in some situations.

To answer your second question, assuming what I have said is the only side effect of revealing $r$, then your method would also allow the verifier to prove things about the sum to another verifier. That may or may not be an issue with your system. There could be other side effects that I am not aware of.


Hiding and Binding key in Groth-Sahai NIZK proof system In context of Groth-Sahai NIZK proof system, I have a couple of doubts on Hiding and Binding keys.

In case of hiding keys (highlighted in red), how is it ensured that $\tau(A) \subseteq \langle u_1,...u_m \rangle$?
In case of binding keys (highlighted in green), how come $\tau \circ p$ be an identity map on $A$? Shouldn't it be an identity map on $B$?

I am still not very familiar with these kinds of proofs, but from what I understood:

1) This inclusion is actually a condition which defines in itself what a hiding key is. That is to say that this paragraph does not say that the inclusion is ensured, but that we should make sure that it is, if we want a perfectly hiding key. However, you may find sets of $u_i$'s that verify this property in the three different instantiations. If you use the short version of the paper where they do not appear, look here instead.

In the second (SXDH) instantiation for instance, to commit in $G_1$, you get $u_1=(\mathcal{P}_1,\alpha\mathcal{P}_1)$ and either $u_2=tu_1$ for a binding key, or $u_2=tu_1-(\mathcal{O},\mathcal{P}_1)$ for a hiding key ($t$ and $\alpha$ are chosen at random). In this last case, $\iota(G_1)\subset \langle u_1,u_2\rangle$ because for $g\in G_1$, you can write $g=\mathcal{P}_1^n$ and then you have $\iota(g)=(\mathcal{O},\mathcal{P}_1^n)=(tu_1-u_2)^n\in\langle u_1,u_2\rangle$. Note that you don't have this with the binding parameters.

2) You are right, they probably meant to write $p\circ\iota$ instead.


XOR and bilinear form property I know that $XOR$ is equivalent to modular addition in the field $\mathbb{F}_2 = \{0,1\}$ (is it right?), and thus should satisfy the following property of a bilinear form:

$$\oplus(u+v,w) = \oplus(u,w) + \oplus(v,w)$$

My doubt is: how has the $+$ in the previous formula to be interpreted? Because if I interprete it like the same $XOR$ (even if looking at the formula it seems not to make much sense), applying the property I think I would have:

$$(u\oplus v) \oplus w = (u \oplus w) \oplus (v \oplus w) = u \oplus v   $$

Even though I was expecting a result like:

$$ u \oplus v \oplus w$$

If the interpretation of the $+$ like the $\oplus$ is not the right interpretation, how has it to be interpreted, even considering that the normal $+$ and the $\oplus$ coincide in $\mathbb{F}_2 = \{0,1\}$?

At the end, what's the meaning of that property?

Actually, as you note, XOR doesn't satisfy the bilinear condition.

What does is multiplication $\otimes$ in $\mathbb{F}_2$, that is:

$$\otimes(u \oplus v, w) = \otimes(u,w) \oplus \otimes(v,w)$$

or, as more traditionally expressed (using $+$ and $\times$ as the field operations):

$$(u+v) \times w = (u \times w) + (v \times w)$$

This is one of the fundamental properties of a field; since $GF(2)$ is a field (with $\oplus$ and $\otimes$ as the field addition and field multiplication), this holds.

And, in $GF(2)$, $\otimes$ is equivalent to bitwise $AND$


How does second pre-image attack on Merkle Signature Scheme work? I understand that a second pre-image attack on the Merkle tree works by creating another Merkle tree using the intermediate nodes as the leaf nodes, and this will lead to the same root hash (public key) being constructed 1. However, I thought that there are two steps to verifying the signature.
Assuming, Winternitz is used as the one-time signature, the one-time signature is first being verified and then following the authentication path to get the root node. Assuming the attacker used the intermediate nodes as the leaf nodes, would this mean that he would have to use that intermediate node (hash of 2 child nodes) as the public key of the OTS.

I am confused as to how the OTS verification would work, does this mean that the attacker has to find a pre-image $x$ so that $H(x) = y$ where $y$ is the intermediate node?
Are there any reference papers talking about this attack on the Merkle signature scheme?

I understand the portion on the merkle tree attack, but for the merkle signature scheme, there is the portion of verifying the OTS first before traversing the tree to construct the root node. My question is on how the attacker can get past the OTS verification given that it seems he has to find a pre image

Hoes does second pre-image attack on Merkle Signature Scheme work?

Lets take a simple example; suppose the attacker sees a valid Merkle signature; in that signature, he sees the bottom-most Merkle tree node of the form:
$$A = H( B, C )$$
where $H$ is the Merkle tree combination function, $B$ and $C$ are the left and right child nodes, and $A$ is the node value.  He also obtains from that signature the authentication path from node $A$ to the root.
The attacker's goal is the generate a forgery; to do that, what he does is generate his own OTS private key, and the corresponding value $X$.  Then, the second pre-image attack is to find a value $Y$ with:
$$A = H( X, Y )$$
If he succeeds, then he can generate a forgery with any message he wants.
What he does is generate the OTS for that message with the public key $X$ (which he can do; he has the private key).
Then, to form the authentication path, the first node of the path is the value $Y$; the rest of the path is copied from the valid authentication path he has seen.
When the validator examines the forgery, he'll compute the OTS public key, which will result in the value $X$.  He will then walk up the authentication path; the first step will be computing $A = H(X, Y)$ (as $Y$ is the value he sees in the authentication path; the rest of the path will proceed precisely as the valid signature, resulting in the expected public key value, and so the signature validates.