Commit and prove as a general trick for malicious security After reading through Lindell's excellent tutorial (https://eprint.iacr.org/2016/046.pdf), I wonder about the following.

To make a protocol secure against fully-malicious security, it seems that forcing parties to commit to their input and then prove knowledge of that input (using a zero-knowledge proof of knowledge) is a useful tool. Basically, the zero-knowledge proof of knowledge allows the simulator to extract the adversary's input and fabricate data as required.

My question is about the usefulness of the zero-knowledge proof in reality. Is the ZK proof only required to make a proof of security go through?

On Page 43, Lindell states that decommitting is essentially the same as that ZK proof. So for a new protocol, is it sufficient to decommit a commitment at some point in the protocol's real-world implementation, but replace the decommitment by a ZK proof in my protocol's security proof?

No, zero-knowledge proofs are not only a trick to prove security: essentially all protocols where zero-knowledge proofs are used would be insecure against malicious adversaries if zero-knowledge proofs are removed, or replaced by "decommitments" as you suggest.

Let me illustrate this on a simple example. Suppose that Alice and Bob have respective inputs $x$ and $y$, which are $n$-bit string. Suppose also that Bob wants to obtain the Hamming distance between $x$ and $y$. For example, Bob could be a server which stores a fingerprint, and it should grant some access rights only to the user which has this fingerprint; hence, the goal of the protocol is to check that Alice's fingerprint is correct (in which case it will be close to $y$ - not necessarily equal due to imperfect measures), but without leaking $x$ or $y$.

A simple solution to the above is as follow: Bob encrypts each bit $y_1, \cdots, y_n$ using, say, the ElGamal encryption scheme "in the exponent" (i.e., an encryption of $y_i$ is of the form $(g^{r}, h^rg^{y_i})$), and sends these $n$ ciphertext to Alice. Now, Alice can homomorphically compute an encryption of the Hamming distance between $x$ and $y$, using the fact that $\mathsf{HD}(x,y) = \sum_{i=1}^n x_i + y_i - 2x_iy_i$, and send back this ciphertext to Bob, who decrypts it and gets $\mathsf{HD}(x,y)$.

Suppose now that Bob is malicious. In this case, he could for example cheat as follow: instead of encrypting $(y_1, \cdots, y_n)$, he encrypts $2, 4, \cdots, 2^n$. It is easy to see that doing so allow him to recover the entire $x$ when decrypting the final ciphertext. To prevent this attack, the natural solution is to use a zero-knowledge proof. With the general commit-and-prove strategy, it would look as follow: Bob commits to $y_1, \cdots, y_n$, proves in zero-knowledge that each commitment commit to the same value that the one encrypted in the corresponding ElGamal ciphertext, and proves in zero-knowledge that each committed value is a bit (i.e., that each $y_i$ satisfies $y_i(1-y_i) = 0$). This guarantees that Bob cannot perform the attack I mentioned. In the proof, this will allow the simulator to indeed extract the $y_i$, but also guarantees that they are bits, and are the value encrypted in the ciphertexts.

Now, if we were simply opening the commitments, all security would break down. Specifically, either Bob commits to the correct $y_i$; but then, when decommitting, he reveals all his private input $y$ to Alice. Or Bob commits incorrect values; but then, Alice has no way to check anything about the encrypted value simply from seeing opening to these incorrect values.


Shannon entropy of string, not same in Binary form? But just as good as a password? This string, "Au+u1hvsvJeEXxky" has a Shannon entropy of 3.75 and a length of 16.

The binary form of the string ( derived from Ascii-table ) is:

01000001 01110101 00101011 01110101 00110001 01101000 01110110 01110011 01110110 01001010 01100101 01000101 01011000 01111000 01101011 01111001

This string has a Shannon entropy of 1.39 and a length of 128.

So while both strings are interchangeable, their entropy differs. Why is
that? And are both strings evenly strong in resisting a brute force guessing attack?

thnx.

I'm going to telepathically make a wild guess.

My wild guess is that you generated the string Au+u1hvsvJeEXxky by asking a computer to choose sixteen characters independently and uniformly at random from the alphabet consisting of a-z, A-Z, 0-9, +, and -, which is, coincidentally, the base64 alphabet.

The distribution on individual characters has 6 bits of entropy per character.  The distribution on strings of sixteen characters chosen independently from this distribution is sixteen times that, namely 96 bits of entropy per string.

If I, as the adversary knowing this information about your process but not knowing the particular outcome, tried to guess your string, I would have a $1/2^{96}$ chance of getting it right.  If I kept trying guesses, the expected number of guesses before I get it right—that is, the average of number of guesses over all possible values of your string—is $2^{95}$.  That's a lot of guesses.

However, as the adversary, I often have more powers than that.  Often, what I have is some hash of your string $H(s)$, and not just yours but $H(s_0), H(s_1), \ldots, H(s_{9999})$ of ten thousand different users who all used the same process.  My goal as the adversary is to find at least one of the strings $s_i$—chances are if I can get a foothold by compromising one user, I can use that to compromise more users in a network.

If I do this intelligently, the cost of my attack—measured in joules, or USD, or EUR—is significantly less than $2^{95}$ times the cost of testing a single guess by evaluating $H$.  With the help of Oechslin's rainbow tables, if parallelized $p$ ways, at least hundred million, I can share work between attacking many targets at once, and it will cost only about $2^{82}$ evaluations of $H$, in the time for about $2^{82}/p \leq 2^{56}$ sequential evaluations.  The Bitcoin network spends this cost in about a year; $2^{56}$ nanoseconds is about two years.

That's a high cost, and a long time to wait, but it's absolutely within the budget of a major corporation or government.  I would recommend making sure that the cost is around $2^{128}$ evaluations of $H$ so that it is completely out of reach of foreseeable human engineering.  There are three ways to do this:

Have every user choose from ${\geq}2^{256}$ possibilities uniformly at random.  For example, instead of sixteen-character base64 strings, use forty-three-character base64 strings.  Or use sequences of twenty words chosen independently uniformly at random from a word list of 7776 words.
Store a salt unique to each user, and use $(\sigma_i, H(\sigma_i, s_i))$ where $\sigma_i$ is the $i^{\mathit{th}}$ user's salt and $s_i$ is the $i^{\mathit{th}}$ user's secret.  This thwarts rainbow tables and prevents the adversary from sharing work between multiple users.
Use a password hash that is costly to evaluate like scrypt or argon2id.

Method (1) is something the users can do.  Alternatively, the computer can choose the user's secret for them, and ask the users to remember it.  Methods (2) and (3) are things that whatever uses the secrets can do—something that the engineers of an application can put into their system to defend it against brute force attacks even if some users choose secrets poorly like human-chosen passwords.

All of the numbers above are premised on the model I telepathically guessed.  Not everyone guesses the same model.  The ent utility suggested by Paul Uszak and an entropy calculator on the web suggested by conchild instead guess the following probability distribution on symbols: probability 1/8 for u and v, probability 1/16 for {+, 1, A, E, J, X, e, h, k, s, x, y}, 0 probability for any other character.  They suggested this by (a) counting the number of appearances of each character in your string, and (b) dividing by the length of your string.  I, instead, used knowledge of common protocols on the internet to guess that you are using the base64 alphabet.  We all assumed independence between characters.  But nobody here knows anything about the process you used.


how calculate plaintext file size from length of encrypted one without decrypting Silly question – is it possible to find out size of original file from encrypted file?  Encrypted with aes-128-cbc.
Looks like there is no way to calculate it. As far as I understand ,all original files with length between let’s say 33 and 47 will have length 48 bytes after aes-128-cbc encryption (should be rounded to next 16 byte block). But, just in case asking the crowd
Update:
Well, I’m not mathematician, just a programmer, and the formula provided in an answer below means not much for me ☹ so I need more plain explanation how I could that.
The story is - I encrypt files (longer than 48 bytes ) by using standard Node.js module (crypto). I ask this module to use aes-128-cbs algorithm (but, generally speaking, I could use others algorithms) and I know the key, the key length, the IV. Looks like I need to read last 2 blocks (32 bytes) of a encrypted file, give them to decipher, it will not be able to correctly decrypt penultimate block due to luck of IV, but should decrypt very last one.
What I suppose to do with this data (last decrypted block)? How EXACTLY I can calculate size of original file knowing content of last block, the key, the key length etc?
Thanks a lot in advance.

As far as I understand ,all original files with length between let’s say 33 and 47 will have length 48 bytes after aes-128-cbc encryption (should be rounded to next 16 byte block).

Actually, if you are using the standard padding pattern (and you don't count the space the IV takes up - you do use a different IV for each ciphertext, don't you), then the range of original plaintext strings will be 32-47; those will all encrypt to 48 bytes, and no one without the key can determine the original length.
However, if you do have the key, you can determine the length without decrypting the entire message; you only need to decrypt the last block - that is sufficient to determine the original length.
That last block is $P_n = C_{n-1} \oplus D_{key}( C_n )$.
For a 3 block message, the savings aren't huge; however if you are trying to determine the exact length of a multi-megabyte plaintext, the savings are more significant...


How does KECCAK operate on a state array filled with zeros? Im trying to implement a sponge in Java. The state starts out as an empty 200 byte array of all zeros. In the KMAC samples document from NIST, the following happens:

(black line is a pdf page break)
The way Im reading this is that a state with a bunch of zeros was sent into KECCAK, and then a state with apparently random data was returned. Does SHA3/KECCAK turn empty data into random data? Am I asking the right questions here? Any help is appreciated.

I personally find the Keccak.team Psuedo Code document very helpful to understand how Keccak-p works.
As DannyNiu said in the comments, most (all?) cryptographic permutation employ "round constants".  These constants are somehow mixed in the Keccak state.
The pseudocode document gives the round constants as a table:
RC[0]   0x0000000000000001  RC[12]  0x000000008000808B
RC[1]   0x0000000000008082  RC[13]  0x800000000000008B
RC[2]   0x800000000000808A  RC[14]  0x8000000000008089
RC[3]   0x8000000080008000  RC[15]  0x8000000000008003
RC[4]   0x000000000000808B  RC[16]  0x8000000000008002
RC[5]   0x0000000080000001  RC[17]  0x8000000000000080
RC[6]   0x8000000080008081  RC[18]  0x000000000000800A
RC[7]   0x8000000000008009  RC[19]  0x800000008000000A
RC[8]   0x000000000000008A  RC[20]  0x8000000080008081
RC[9]   0x0000000000000088  RC[21]  0x8000000000008080
RC[10]  0x0000000080008009  RC[22]  0x0000000080000001
RC[11]  0x000000008000000A  RC[23]  0x8000000080008008

and explains how they are used.  In the iota-step of the $n^\text{th}$ Keccak-p round, the $n^\text{th}$ round constant $RC[n]$ gets introduced and gets XOR'd into the first word, first lane.
Apart from the round constants, the Keccak permutation has a very good diffusion: a single bit somewhere in the initial state will contribute significantly to many output bits.
The combination of both means that your Keccak permutation looks very random.  It cannot, of course, turn zero entropy into random, since no finite algorithm can do that, but the goal of Keccak is to mix things about and make them appear random.


Compact Schnorr signature? The commonly-used ECDSA signature consists of 2 scalars $(r,s)$. There's also a Schnorr signature. Given private key $k$, public key $C = [k]G$ and the message $M$:

Generate random scalar $k_1$
Calculate the $C_1 = [k_1]G$
Calculate the challenge $e = H(C_1 \mathbin\Vert M)$ where $H$ is a selected hash function
Calculate $k_2 = k_1 + e\cdot k$
Signature is $(C_1, k_2)$

The verifier then verifies that $[k_2]G = C_1 + [e]C$

Both schemes seem to be nearly equally secure. I like more the Schnorr's scheme, because it uses nothing more than just a common ECC arithmetics. However the drawback is that the signature is bigger: instead of 2 scalars it's now scalar + point (with 2 coordinates).

One way to solve this is to store the curve point in a compressed way: its $x$ coordinate and the sign bit, from which the $y$ coordinate may be recovered. But this requires extra calculations.

I thought about an easier way. Let's just store the $x(C_1)$—the $x$ coordinate, and the challenge formula should be adjusted to account only for $x(C_1)$.

The verifier should verify the following: $x([k_2]G - [e]C) = x(C_1)$. That is calculate the left-side curve point, take its $x$ coordinate and compare to the signature.

Is this a common practice? Is there a potential flaw in this scheme?

This would work, but note that your weakening verification (slightly). Instead of only $(C_1,k_2)$ being a valid signature, now also $(-C_1,k_2)$ is valid. If you want to do signatures by only using $x$-coordinates you can use the qDSA signature scheme, which indeed saves a few bits in the signature size and public key.

There is actually a more serious compression of Schnorr signatures, which I think is quite common. It is already described in Schnorr's original paper. Instead of having a signature $(C_1,k_2)$ we use $(e,k_2)$, where it actually suffices to have relatively small $e$ (say 128 bits for 128-bit security level). Now we can verify by computing $\bar C_1 = [k_2]G - [e]C$ and checking that
$H(\bar C_1\,||\,M) = e$.

This leads to a 48-byte signature as opposed to a 64-byte one, so saves significantly more than a bit. A downside is that you cannot batch-verify signature anymore, though I don't know if that's actually used in practice.


What makes an algorithm "fast in software" vs. "fast in hardware"? When reading about different algorithms, I often encounter claims that various algorithms are "fast in software" (e.g. Salsa20) or "fast in hardware" (e.g. DES). What properties make a cipher relatively faster in hardware or faster in software? Why would something be fast to implement in hardware but much slower in a software implementation?

"In software" means programming the cipher on a multifunctional processor or smart chip. The normal instruction set is used to build the algorithm, and not available operations have to be emulated.
"In hardware" means building the cipher in real hardware, like on a Field-programmable gate array (FPGA) or Application-specific integrated circuit (ASIC).
(Nearly?) all ciphers are faster in hardware than in software, but we say "fast in software" if an algorithm is not much slower in software than in hardware.

Some operations can be done fast in software, some other are hard to emulate for the typical x86 (or x86-64) processor. A few examples:

Bit shifting (with a constant length) is one of the fastest things in hardware. You can just connect the outputs with the appropiate inputs on the silicon, no transistors needed. Only the speed of the input / output and the current limits this kind of operation, while in software you have to "waste" an entire CPU cycle.
Additions are pretty fast in software, because that's what processors are made for. Higher integer performance was the main goal of CPU optimizations in the past and is even now of high priority. Additionally it's pretty costly to implement big bit size adder because of the carry over. All this makes addition preferable for software implementation.
Permutations are slow in software, but very fast in hardware. It's the same like bit shifting in hardware, but slow in software because there's no specialized operation for permutations. It has to be emulated, and that's pretty costly. Here's a document about fast software permutation instructions. With this a CPU could be much faster at this task.

Other important factors are as example Pipelining. This can enhance the performance on hardware (and limited in software) and reduce the needed area of the chip. All this factors lead to the fact that some ciphers are "faster in hardware" than "in software" or the other way round.


Mapping between NIST test and TRNG features Each of the NIST tests are generally explained in Random Bit Generation - Guide to the Statistical Tests. I was wondering if some one can help me understand them better. For example, which tests show the robustness, independence, ergodicity, stationarity, etc.

Based on the description provided on NIST website, I think, the mentioned features can be understood from following tests:

robustness: cumulative sum test
independence: random binary rank test
ergodicity: Maurer's universal statistical test or linear complexity test
stationarity: cumulative sum test

I was wondering if these are correct. In addition, if other NIST tests can be summarized.

It's difficult to map each of the 15 tests to a particular qualitative descriptor. Adjectives like robust are not mentioned in the 800-22 documentation.

The null hypothesis of randomness ($H_0$) in all tests fundamentally requires samples from a stationary and ergodic process. Otherwise the tests would be inconsistent with respect to time, and could not accurately model the samples' shifting distributions or test score expectations.  Or the test scores for this million bits would differ widely from that million's. Although be mindful of some variability implicit in any random process.

The requirement for independence within each test varies though. §2 of 800-22 details the mathematical assumptions underpinning each test. NIST doesn't always highlight the level of significance of independence within each test.  They often don't attempt to debate the causality of a $H_0$ sequence, just it's effect and characteristics.

Some are explicitly discussed.  The Discrete Fourier Transform (Specral) test is an example of a test that specifically targets independence in the mathematical sense.  It looks for correlations between samples spaced $n$ samples apart.  Maurer’s "Universal Statistical" test is similar, exploiting correlation for compressibility. As is the Binary Matrix Rank test. Conversely the Frequency (Monobit) test doesn't.  It will accept any degree of correlation as long as the ones and zeros are evenly matched in line with a half normal distribution.

The sensitivity to independence is harder to identify with some of the other tests. You may have to decompose the statistics beneath  tests like the Serial or Cumulative Sums (Cusum) tests.

Don't confuse the recommended input lengths with non ergodicity.  The recommendations are there simply to facilitate some of the test metrics' reference distributions, or to limit processing time.


What is the high level procedure to use ECDSA? I want to make a computer program to sign and verify some message using ECDSA.

There are some computer libraries but I'm having trouble using them, as I don't understand ECDSA.

What do I need theoretically?

Is ECDSA the same as other digital signing that I calculate hash of message, encrypt the hash and append it to the original message?
In ECDSA can I choose hashing function and some encrypting parameters? What I need to know about generating pair of keys? What else do I need to specify.

NOTE: I don't need to implement ECDSA algorithm, there are libraries for that, but what I need to know what are the variable parameters in the algorithm.

EDIT: Here is a note from the library:

sign = crypto.createSign('SHA256');

privateKey = getPrivateKeySomehow();

sign.write('some data to sign');
sign.end();

sign.sign(privateKey);
// Prints: the calculated signature using the specified private key and
// SHA-256. For RSA keys, the algorithm is RSASSA-PKCS1-v1_5 (see padding
// parameter below for RSASSA-PSS). For EC keys, the algorithm is ECDSA.

Does this mean I have to specify a hashing algorithm and also generate a pair of EC keys?

Is ECDSA the same as other digital signing that I calculate hash of
  message, encrypt the hash and append it to the original message?

No. From a user standpoint, you give the ECDSA module the message, it will hash it internally and then do some black magic with it (which includes drawing a random number) and output you a signature. If you want to test if your implementation is decent, ie does the hashing by itself, take a long message (like a couple of kB long) and give it to the function. If it "just works" then it is hashing, if not, well then it is not hashing.

  In ECDSA can I choose hashing function and some encrypting parameters?
  What I need to know about generating pair of keys? What else do I need
  to specify.

Theoretically you can choose the hashing function, practically things may get a little more difficult with SHA1 and SHA256 being the standard options for ECDSA (despite SHA1 being broken).

Key generation is straight-forward. You pick one of the named curves your library provides (preferably the number in its name should be larger than 240) and then call the function to generate the key. This function will then generate the public / private key pair for you, by drawing a random number and doing an operation known as "scalar multiplication". Do not try to generate a curve yourself, this is really hard to do. The "larger than 240" limitation should give you a curve with 120-bit or more security which is sufficient.


ECC vs RSA: how to compare key sizes? I know and I have understood the details of RSA, elliptic curve cryptography, (EC)DH and (EC)DSA.

I keep reading everywhere that (if we don't consider non-deterministic computers) "ECC can achieve the same level of security as RSA, but with lower key sizes". While I can guess why this is true, how do we mathematically prove that?

Here's what I think:

The fastest algorithm for the ECC discrete logarithm problem is the Baby-step Giant-step, which is $O(2^{b/2})$ (https://en.wikipedia.org/wiki/Baby-step_giant-step).
The fastest algorithm for the RSA problem/integer factorization is $O(\exp((64 b / 9)^{1/3} \cdot (\log b)^{2/3}))$ (http://en.wikipedia.org/wiki/Integer_factorization).

Here $b$ is the bit-length of the key/of the group order.

Therefore, an ECC key of $b_1$ bits has the same strength of an RSA key of $b_2$ bits when: $2^{b_1/2} \approx \exp((64 b_2 / 9)^{1/3} \cdot (\log b_2)^{2/3})$.

Using that formula I can calculate that if I have a 2048-bit RSA key, I can achieve the same level of security with a 273-bit ECC key. But this number (273) is too high.

My question is: is my reasoning wrong? Where is the mistake?

Your calculation is broken.

First as pointed out correctly the expected run-time of GNFS (general number field sieve) is: $$\text{O}\left(\exp\left[\left(\sqrt[3]{64/9}+\text{O}\left(1\right)\right)\cdot \sqrt[3]{\ln n}\cdot (\ln \ln n)^{2/3}\right]\right).$$

So next you can't just set these $\text{O}$s equal, as $\text{O}\left(f\left(x\right)\right)$ means $\text{O}\left(f\left(x\right)\right)< kf\left(x\right)$ which means this is an asymptotic upper bound meaning you need some reference point to find out the "$k$".

Now you'd need some way of comparing the "strengths" of the algorithms. In the paper of Lenstra and Verheul this is done using a reasonable recent attack on the cryptosystems, yielding the information that 1024 / 512 bit RSA takes needs X MIPS-Years and breaking 128-bit ECC takes Y MIPS-Years. Now as you know the growth functions you can calculate how the effort grows to obtain the effort you want to meet. This effort can be set equal to get a complex relation, which can only be solved numerically.

First data point: 512-bit number needs $10^4$ MIPS-Years.
Second data point: 108-bit attacked in $8\cdot 10^6$ MIPS-Years.

Formulas:

\begin{array}{lcr}
E_{\text{RSA}}\left[2^{512}\right]={10}^4 & \Longrightarrow & \frac{E_{\text{RSA}}\left[2^x\right]}{E_{\text{RSA}}\left[2^{512}\right]}=\frac{X}{{10}^4} \\
E_{\text{ECC}}\left[2^{{108}}\right]=8 \cdot {10}^6 & \Longrightarrow & \frac{E_{\text{ECC}}[2^y]}{E_{\text{ECC}}[2^{108}]}= \frac{X}{(8\cdot {10}^6)} \\
\end{array}

Solving this for $X$ yields
$$\frac{(8\cdot {10}^6)\cdot E_{\text{ECC}}\left[2^y\right]}{E_{\text{ECC}}\left[2^{108}\right]}=\frac{10^4 E_{\text{RSA}}\left[2^x\right]}{E_{\text{RSA}}\left[2^{512}\right]},$$
where $E_X\left[Y\right]$ denotes the effort required to attack the number $Y$ of scheme $X$ in MIPS-Years.

For $E_{\text{ECC}}\left[2^x\right]$ this is defined: $E_{\text{ECC}}\left[2^x\right]=2^{x/2}$ and for RSA on simply inserts $2^y$ into the formula of paragraph 2 (without the $\text{O}$).

My calculations yielded a 168-bit EC-key for 2048-bit RSA key, which is correct according to the Lenstra and Verheul paper if you want to compare now. They also consider comparing with "cryptanalytic progress for ECC enabled" yielding ~200 bits.


MITM defense in Diffie-Hellman protocol Let's consider that Alice and Bob both know a shared secret $secret$ and don't know each other DH public keys. They want to authenticate each other and their keys using only $secret$. Let's also forget about an existence of SMP. Can the following scheme be considered secure?

First, Alice and Bob perform Diffie-Hellman KE:

$Alice: send(g^a)$
$Bob: recv(g^a);\ send(g^b)$
$Alice: recv(g^b)$ // Now both Alice and Bob has a shared $dh\_key$

Next, they want to be sure that their companion:
a) Knows a shared secret.
b) Is the owner of the corresponding DH private key.

$Alice: send(HMAC(g^a, secret))$
$Bob: recv\_and\_check(msg, secret); send(HMAC(g^b, secret))$
$Alice: recv\_and\_check(msg, secret)$

If all checks are passed Alice and Bob can start a secure data exchange. They also can save DH-public keys for future conversations.

So:

Is the scheme secure?
If the answer to the first question is 'yes' what are pros and cons in comparison with SMP (like in OTR SMP)?

Since you tagged the question with "man-in-the-middle" then the answer is that the protocol is not secure after its first use because the eavesdropper can record the exchange and repeat it. Instead, each party should challenge the other party with a random value that will be used by the other party to construct the HMAC.


Information leakage from the ecryptfs filesystem I'm wondering what information might be leaked from the ecryptfs filesystem. This is what Ubuntu uses if you check the box for "encrypted home directory" when using the desktop installer, so is probably quite widely used. Key characteristics of it:

each file is encrypted individually and stored in the underlying filesystem
each file is padded in size to be a multiple of 4096 bytes, with a minimum of 12288 (except for directories and soft links)
file and directory names are encrypted
the directory structure is maintained

(Note I haven't found a spec about the above, this is worked out from observing my own filesystem - it's stored in /home/.ecryptfs/USERNAME/.Private if you want to examine your own).

So assuming you can't break the encryption keys then you can't examine the contents of the files. However there is still some information left to examine, and just as traffic analysis can deduce useful information from encrypted communications data, I'm wondering how much someone might be able to work out from the directory structure and approximate file sizes.

Certainly you could work out which directories and files contained music, video and photographs from file size. You might even be able to work out what music and videos existed. You could probably work out some of the applications in use due to their pattern of config/cache directories - firefox vs chrome etc.

Is there anything else? Is there a standard analysis of what could be deduced? Does anything else spring to mind?

(I must admit I assumed there was no padding of file sizes when I started writing this question - I'm reassured that there is).

(Disclosure: I'm the author of the functionality that you're asking about (good question!).)

Ubuntu's Encrypted Home Directory feature uses eCryptfs as the filesystem encryption technology.  eCryptfs is a layered filesystem built directly into the Linux kernel.  It mounts one directory on top of another.  The top directory is really just a "virtual" mountpoint.  Applications (and humans) can operate within that directory and read and write data without needing to know or be bothered by the encryption that's happening underneath.  The lower directory is where the actual encrypted files are stored on disk.

This approach has several advantages.  Unlike dmcrypt or full disk encryption, you don't have to pre-allocate a fixed amount of space dedicated to encryption.  You can also limit what gets encrypted a bit more to the information that's truly unique to you (improving overall system performance and power consumption).  There is some privilege separation between users, with each user having their own unique mount point and encryption keys.  And this particular feature is hooked into PAM, so that your directory is mounted automatically when you login, and unmounted when you logout.  Also, each and every file is encrypted with a unique, randomly generated key called the 'fek' (which is stored in the header of the file, and wrapped with the MOUNT passphrase).  What this means is that two cleartext files that are binary equivalent encrypt to two completely different ciphertexts!

On the flip side, there are a few things that you should be aware of -- now to the meat of your question!

The upper and lower file structure is pretty much identical, and some file names might be deduced (based on the default Ubuntu home directory skeleton)
File permissions, file ownerships, and file timestamps are not encrypted (so files with weird permissions, like 0123 might stand out)
Encrypted filenames limit the upper cleartext filename to about 160 characters (as the filename encryption requires some padding)
Swap should absolutely be encrypted, if you're using Ubuntu Encrypted Home, as anything in memory can be swapped to disk at any time (and certainly is, if you hibernate a system)
When the filesystem is actively mounted, only Unix run time Discretionary Access Controls  protect you from other users on the system (note that the home directory is permission 0700)
When the filesystem is actively mounted, eCryptfs does NOT protect you from the root user
Unless you move your ~/.ecryptfs/wrapped-passphrase off the local system and onto removable media (like a usb stick or flash disk), your LOGIN passphrase is the weak point of the encryption

Now, all that said, I still believe that Ubuntu's Encrypted Home delivers an outstanding balance of security and usability.  It's trivial to setup, and with a good login password, it provides extremely strong protection of all of your data in $HOME against off line attacks.  In other words, if someone physically steals your laptop, boots a live CD and starts digging around your $HOME/.Private encrypted data, they might glean some information about your filenames, directory structure, and timestamps.  But to obtain the contents of any particular file, they will need one of:

your LOGIN passphrase and your wrapped-passphrase file
the cleartext, 128-bit long, random MOUNT passphrase (stored inside of the wrapped-passphrase file)
enough time to brute force the 128-bit key in 2.
flaws in AES256

For more information, I've written magazine articles and a running series of blog posts on eCryptfs.


Does AES encryption work like a padlock or like a safe? If I encrypt a plaintext p using AES-256 in GCM mode with the keys $k_1 ... k_n$ and I want to decrypt it later, can I use the keys in any order when decrypting or do I have to use the same order as when encrypting but in reverse?
If not, is there a modern symmetric encryption algorithm that lets me perform the decryption in any order?

Mode Dependency
Whether or not the order of AES encryptions matters depends on its mode of operation. I'll get to your case of GCM (Galois Counter Mode presently).
"Safe-like" modes
For modes such as ECB, CBC, or PFB where the plaintext contributes to the input for the actual primitive, then the order does matter.
"Padlock-like" modes
For some streaming modes such as CTR and OFB then the order does not matter as the XOR of streams of bits can be done in any order and so if the streams are independent of the plaintext things can be done in any order.
ETA: @fgrieu points out that such modes use an additional parameter known as an Initialisation Vector or IV and that I have implicitly assumed that these are not encrypted during the multiple encryption processes. This assumption is not consistent with implementations that simply pre-pend the IV to the ciphertext in the cryptogram, nor certain theoretical constructs. It would be more accurate to say that if $p$ is encrypted with key, IV pairs $(k_1,IV_1), (k_2,IV_2),\ldots, (k_n,IV_n)$ then the padlock property applies.
GCM Mode
Your case of GCM is interesting as it provides two cryptographic functions: confidentiality and authentication. The confidentiality part is unaffected by ordering as it is a stream like CTR that is independent of plaintext. Thus you can recover $p$ by decrypting in any order (assuming that no-one modifies any ciphertext outside of decryption). However, the authentication part does depend on the ordering and so the final decryptions and intermediate decryptions should throw up error warnings if they are done in anything other than the reverse order. Again we must specifically exclude the IVs used in GCM from encryption for the padlock property.
If you intend to ignore these authentication tags (which is always poor practice), you would be better served by using an unauthenticated method such as CTR and finding a suitable, non-integrated authentication scheme for your application. This will shorten the ciphertext as each GCM encryption adds its own authentication tag which lengthens the final message by $n$ blocks.
Additional Commentary
Generally speaking, applying multiple layers of encryption is not something that is recommended as meet-in-the-middle attacks means that the overall security is not additive. I suspect that you might be considering single-encryptor-group-decryptor scenarios and you might like to read up on ideas such as Shamir's Secret Sharing.


How does padding oracle attack work with bytes larger than possible length? I am trying to understand how the POODLE attack would actually be implemented. In the original security advisory from Möller, Duong and Kotowicz [POODLE 14] the following example is presented:

Assume that each block $C$ has 16 bytes, {..}. The MAC size in SSL 3.0 CBC cipher suites is typically 20 bytes, so below the CBC layer, an encrypted POST request will look as follows:
POST /path Cookie: name=value... \r\n\r\nbody || 20-byte MAC || padding

Then the authors go on explaining how one can decrypt a previously unknown byte of the cookie:

The attacker then replaces $C_n$ by $C_i$ and forwards this modified SSL record to the server.

I understand it so far. The only problem I have is this, since the padding is 1 to L bytes long (where L is our block size in bytes, 16 in our example) we only can decrypt bytes with values between 1 and L right ? Let's say the last byte in the block $C_i$ equals to 0x0020, how would I decrypt it ?

For a CBC mode cipher, which is what POODLE applies to, you don't encrypt or decrypt individual bytes, but rather blocks, formed by adding padding to the actual data bytes. For encryption in general every byte can be any value 0 to 255, and the SSL spec allows the padding_length byte to be almost any value, but most if not all implementations only use 0 to L-1. (Not 1 to L; a different common padding scheme, PKCS#5/7, does use 1 to L.) SSL/TLS uses MAC-then-encrypt (see a hundred other questions why this turned out to be not the best choice) so actually user-data plus HMAC is padded and then CBC-encrypted, as shown by the line you posted: user data consisting of POST /path cookies etc, then (20-byte) MAC, then padding.

CBC mode encrypts a block at a time after XORing the plaintext block with the previous ciphertext block, or for the first block with the IV. Similarly when decrypting it XORs the decrypted block with the previous ciphertext block or IV to produce the plaintext. The diagram in Wikipedia shows this in detail.

HOW POODLE BITES. You omitted most of the paper's explanation:

  The attacker controls both the request path and the request body, and
  thus can induce requests such that the following two conditions hold:
  ● The padding fills an entire block (encrypted into Cn). ● The
  cookies’ first as-of-yet unknown byte appears as the final byte in an
  earlier block (encrypted into Ci). The attacker then replaces Cn by Ci
  and forwards this modified SSL record to the server. Usually, the
  server will reject this record, and the attacker will simply try again
  with a new request. Occasionally (on average, once in 256 requests),
  the server will accept the modified record, and the attacker will
  conclude that DK(Ci)[15] ⊕ Cn-1 [15] = 15, and thus that Pi[15] = 15 ⊕
  Cn-1 [15] ⊕ Ci-1 [15]. This reveals the cookies’ first previously
  unknown byte. The attacker proceeds to the next byte by changing the
  sizes of request path and body simultaneously such that the request
  size stays the same but the position of the headers is shifted ,
  continuing until it has decrypted as much of the cookies as desired.
  The expected overall effort is 256 SSL 3.0 requests per byte.

When Cn is replaced by Ci satisfying the two stated conditions, the receiver first decrypts, and unpads, the received message. There are two possibilities:

If the result of CBC decryption has anything other than 15 in the last byte, the unpadding either fails entirely or yields a result that fails MAC verification (with overwhelming probability), producing an error alert that the attacker can observe.
If the result of CBC decryption does have 15 in the last byte, the receiver doesn't detect any error and continues with the session. The attacker now knows that the last byte from the previous ciphertext block (Cn-1[15]) XORed with byte 15 of the block that was encrypted to form Pi (Dk(Ci)[15]) is 15 and also knows that Dk(Ci)[15] was computed as Pi[15] XOR Ci-1[15]. Combining these allows the attacker to compute Pi[15] with the formula shown.

Replace 16 and 15 by 8 and 7 for an 8-byte block cipher, which for SSLv3 was triple-DES, DES, RC2 or IDEA. But almost nobody implemented IDEA and RC2, and DES has been insecure and deprecated or prohibited for over a decade.

The attacker now knows a cookie byte (or bite?); rinse and repeat, or as a classic snack advertisement had it, "munch all you want, we'll make more".
EDIT: Specifically, to get the second cookie byte, the attacker adjusts the URL path that it causes the browser to request, so that the second cookie byte now falls at Pi[15], satisfying the second assumption. It repeatedly requests this URL until it gets the Pn'[15]=15 case for the second cookie byte. Then it adjusts the path so that the third cookie byte falls at Pi[15] and is recovered, then the fourth, and so on. Remember the browser sends the same cookie(s) on all requests to the same origin across multiple connections, until directed to change it(them), typically when the user logs-out or after a long period of time like an hour; this attack likely takes less than 50*128*0.1sec = 10 minutes. This does assume that the other data in the request headers like user-agent: and accept-language: etc don't vary in length (or vary only by a multiple of the blocksize 16, less likely); in practice on most browsers these are fixed except for Host: and that is fixed by the attack. It doesn't matter the key (and IV) changes on each connection, because we don't try to recover any of those keys, only an unchanging part of the plaintexts.


Is double encryption really a bad idea? Are meet-in-the-middle attacks practical at all? Meet-in-the-middle attacks are used to justify that attacks on ECC and double encryption will have complexity of $O(\sqrt{n})$ for ECC and $O(2^{n+1})$ for double encryption complexity instead of $O(n)$ and $O(2^{2n})$, respectively.

From my understanding (and please correct me if I'm wrong), meet-in-the-middle attacks rely on storing the results in a map. For example, if we double-encrypt with DES, we precompute all possible encryptions with all keys (which is $2^{56}$ possibilities), put them in a sorted map, and then decrypt with all possible keys, and see which of the decryption intermediate cipher-texts match what we have in the map. Given that map searches are $O(\log{n})$, then we have no problem.

I get this is possible for DES, albeit it's super-hard. We'll need around 500 TB of memory to do this. Well, let's say the NSA has that.

But why is the meet-in-the-middle attack taken seriously at all with ECC and AES, when they have 160 or 128 bit at least? If we used all earth's atoms to build SSDs to store all the map information I discussed up there, it probably won't be enough.

My question is basically: Is double-encryption a stupid idea given all these practical limitations when talking about encryption algorithms other than DES that have relatively long keys? And for ECC, is it true that ECC can be broken with $O(\sqrt{n})$ complexity?

meet-in-the-middle attacks rely on storing the results in a map

Only the naive version of MitM does.

The impractical memory requirement (size and accesses) of naive MitM can be greatly lowered with a relatively modest increase in other computation costs, and the calculation distributed to independent devices. The reference paper is Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, 1999). It covers MitM in section 5.3.

That's also discussed in this question.

  Is double-encryption a stupid idea

Largely so, because of MitM with such improvements. In the case of AES, using AES-256 is a much better idea than double AES-128: it foils MitM, and is faster.

  Is it true that ECC can be broken with $\mathcal{O}(\sqrt{n})$ complexity?

Yes, that's the cost of solving the Discrete Logarithm in a general cyclic group of order $n$, including defined using point addition on an Elliptic Curve. The reference method is Pollard's rho. That is seldom identified to MitM (as the question does), but there are similarities. Not coincidentally, parallel Pollard's rho is described in section 5.1 of the above paper.


Can OTP be used with RSA Considering that a PKI has already been established, why can't we use RSA to send the One Time Pad instead of using AES?

It makes sense to me since:

A trusts the CA which is providing the identity of B
and vice versa
A obtains the public key of B from the Certificate and uses it to encrypt the pad
B decrypts the message and obtains the pad

Is this possible?

The one time pad can be used to provide perfectly secure encryption, given fully random key stream. Of course this key stream needs to be kept perfectly secure for it to be considered fully random.

Nether RSA nor AES can be used to protect a one time pad, because the one time pad would rely on RSA and AES to be secure. Neither RSA nor AES are perfectly secure, and neither can even be proven to be secure - as far as we know.

This prohibits distributing a one time pad with either RSA or AES; you are better off just using RSA / AES directly, for instance using a hybrid cryptosystem with AES in counter mode or any authenticated mode.


Golomb's Randomness postulates In Handbook of applied cryptography, Golomb's randomness postulates are given:
Let $s$ be a periodic sequence of period $N$. Golomb’s randomness postulates
are the following.

R1: In the cycle $s_N$ of $s$, the number of $1$s differs from the number of $0$s by at most $1$.

R2: In the cycle $s_N$, at least half the runs have length $1$, at least one-fourth have length $2$, at least one-eighth have length $3$, etc., as long as the number of runs so indicated exceeds $1$. Moreover, for each of these lengths, there are (almost) equally many gaps
and blocks.6

R3: The autocorrelation function $C(t)$ is two-valued. That is for some integer $K$, $C(t)=K$ for $t\neq 0 \pmod N$ while $C(0)=N.$

But why do those postulates make sense?

They make sense as a starting point, for pseudorandomness.

R1. This is a strict balancedness condition, the difference is 1, in case $N$ is odd and zero is impossible.

R2. If you have an i.i.d. and unbiased binary source, the run length distribution is geometric, which in a finite length segment should follow the profile given in R2, due to the law of large numbers.

R3. Having an autocorrelation $C(t)$ of the form
$$
C(t)=N I\{t=0\}+ f(t) I\{t \neq 0\}
$$
where $I$ is the indicator function, with $f(t)$ small in absolute value is a feature of an i.i.d. independent sequence.
By parseval $|f(t)|\leq 1$ is possible for odd lengths. Golomb chooses this off peak correlation function $f(t)$ as constant so phase information is not leaked.

Of course he also knew that algbraic structures, in particular cyclic difference sets, allowed one to mechanise this two level correlation.


Security of tokenization of plain text conversations - cryptanalysis I came across a marketing video here. They claim to perform AES encryption and tokenization of sensitive data, at the corporate gateway, before it leaves the company firewall destined for the public cloud. So keys and token<=>plain text mapping tables remain at gateway and cipher text/tokens live in the public cloud.

The purposes of this question is to understand the real security of the product than just what is claimed. The video link is there but I've put screenshots below on the relevant portions. I did some basic analysis by simply eyeballing the video and seems the security is rather poor. You can clearly see, just from their public demo videos at the 2:19 mark, that

all strings are dropped to lower case => tokenized
letter casing 'flips' are then encoded (bitfield?) and appended to the token (eg "flip case of 1st character")
the token is wrapped within pre/post ambles or delimiters

Full resolution: https://i.imgur.com/6ZWXz3H.jpg

NOTE: Image is being referenced lawfully. Considerations include, but are not limited to, sections 107 through 118 of the copyright law, Title 17, U. S. Code. In particular, section 107 provides for lawful reproduction for the purposes of criticism, research as well as commentary.

The supposed security of such a system is that despite access to the "data in the cloud", no information is revealed. However, even without access to clear text counterparts, it should be fairly trivial to sort the "secured" tokens, drop the case encoding information, and then perform a frequency analysis and mapping it to regular English histograms. Presumably this is how they do their "search and sort, even inside encrypted data" feature.

My questions are:

How serious do you consider such a security system?
How many words/tokens of such "secured tokenized" data are needed to statistically decipher everything (with say, 90-95% confidence) assuming access to only tokenized data?
Any particular reason to encode the tokens in Chinese? I would do that to visually consume the space of one character (in browsers for humans) while still encoding 2-3 bytes per UTF-8 character.

Chinese "looks" encrypted. I believe it to be a marketing gimmick; they want to be able to show "encrypted text" that people will unconsciously associate with notions of unreadability and utter obscurity -- and nothing beats Chinese for that (except in China, of course; if they want to sell their product to China they will have to use Greek or Sumerian scripts).

There are more than 70000 Chinese characters in Unicode, but only 20000 or so in the "first plane" (the code points which fit on 16 bits), which are the most likely to be supported by existing software. This still allows for 14 bits worth of data in each glyph, which is not bad.

As your analysis shows, this appears to be a simple word-based substitution cipher, which will be broken by statistical analysis. People use perhaps 2000 common words, so I suppose that observing a corpus of, say, 30000 tokens ought to be enough to decrypt the whole thing, especially since there is an awful lot of context (on your screenshot we even have the pictures of the individuals involved !). Minoen "Linear B" script was unravelled with less data than that.

No, it is not secure, and hardly "serious".


One-time pad and Perfect secrecy Consider the following property of one-time symmetric encryption scheme $(\mathsf{Enc}, \mathsf{Dec}, \mathsf{K})$. For Every message distribution $M$, every pair of messages $m_0,m_1$ belonging to $M$ and every ciphertext $c$ belonging to $C$, it holds that:

$$\Pr[M=m_0 | C=c] = \Pr[M=m_1 | C=c]$$

Argue that the above property is not a characterization of perfect secrecy via a counterexample. Consider the one-time pad and any non-uniform distribution over $\{0,1\}^j$.

Hint:

Combine the usual definition of perfect secrecy $$\Pr[M=m\mid C=c]=\Pr[M=m]$$ with a non-uniform distribution $M$, e.g. $\Pr[M=0]=0.25, \Pr[M=1]=0.75$.


Public keys and their protocols I'm having difficulties understanding exactly what this protocol means:

$S \to D : \{N_S , S\}K_D$

$D \to S : \{N_S , N_D \}K_S$

$S \to D : \{N_D \}K_D$

"where $S$ represents the supervisor’s console and $D$ represents the door controller and the other symbols have their usual security protocol meanings."

I understand $N$ to be a nonce, a randomly generated number/hash that will only be used once.

I'm assuming $K$ is the public key?

Could someone explain this protocol for me, I’ve looked everywhere and cannot find anything like this.

It seems like an authentication protocol. In the first message, $S$ identifies herself. In the 2nd message $D$ proves knowledge of her private key (otherwise she could not return $N_s$. In the third message, $S$ proves knowledge of her private key.

You asked in a comment about replay attacks. There are two possibilities, the attacker is impersonating $S$ or $D$.

For $S$, the attacker might replay a captured 1st message. $D$ would see it, decrypt, return $N_S$ with a randomly generated $N_D$. The attacker could not possibly know what $N_D$ is and could not send the last message.

For impersonating $D$, $S$ would send the first message, but the attacker couldn't decrypt it and therefore could not send the 2nd message.

So, it seems the protocol is secure against replay attacks.


ECC key size and signature size My understanding of ECDSA signature length is that it depends on the key size. So for instance, if a "prime256v1" is used, the signature length will be 64 because (n/8)*2 and for "secp384r1" it will be 96. However, I don't understand why is it for "secp521r1" the signature length is 132 instead of 130?

An ECDSA signature consists of two integers that can range between 0 and $n$, where $n$ is the curve order.

For secp521r1, the curve order is just a shade under $2^{521}-1$, hence it requires 521 bits to express one of those integers, or 1042 to express two.

130 bytes would not be sufficient, as that has only 1040 bits.

131 bytes would suffice; however the convention is to express those two integers separately; each integer takes up 66 bytes, and hence 132 is used for the two.  You could combine the top byte of each integer into a single byte (as the top byte of each integer is either 0 or 1), reducing the signature size to 131 bytes; however I haven't heard of anyone bothering.


Collision-free one-wayish function mapping 32 bit to 32 bit As simple as it may sound, I was unable to find a collsion free one-way(ish) function which takes 32 bits of input and produces 32 bits of output. I apologize if I just didn't knew the right keywords to find the function.

Of course, $2^{32}$ is within a range which can be easily bruteforced within a couple of seconds on modern mid to high end retail PC's but the goal is to not let attackers find the input in a way faster than bruteforce.

Also the function should be proven to be collision free, which can be achieved by bruteforcing each $2^{32}$ input. I'm willing to take that task upon me if someone hasn't got the time to do so (or just doesn't want to).

EDIT: I forgot to mention the attack scenario and already discarded ideas:

The function will run in a white-box enviroment so I'd rather not use functions relying on keys to be secure (like Pseudo-Random-Permutations).

I also tried turncating hash functions like SHA-2, Keccak or the underlying hash function of ChaCha. Sadly, all of them have collision when being truncated to 32 bit.

The function will be used to obfuscate if-statements by comparing the outputs of the function.

It is wanted a permutation of the 32-bit integers that is sizably more difficult to compute in the reverse direction than it is in the forward direction. Obviously, the ratio can't be more than $2^{31}$, since that's the cost of reversing the function by brute force. Also it is useful that the thing is parametrized; otherwise, it could be tabulated, and even reduced to a rainbow table.

I propose a construction using the Discrete Logarithm Problem in $\Bbb Z_p^*$ and cycle walking.

Let $p$ be a prime with $q=(p-1)/2$ prime and $p\bmod8=7$ (which implies that $2^q\bmod p=1$, and $2$ is a generator of the subgroup of quadratic residues modulo $p$, of prime order $q$). The function $f_p$ defined for integer $x$ by
$$x\mapsto f_p(x)=\min\big((2^x\bmod p),\,p-(2^x\bmod p)\big)$$
is a permutation of the integers in $[1,q]$ which is easy to compute in the forward direction, but requires solving the DLP in $\Bbb Z_p^*$ to reverse. Illustration for $p=47$

   x =  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
fp(x)=  2  4  8 16 15 17 13 21  5 10 20  7 14 19  9 18 11 22  3  6 12 23  1

This property also holds if we add two parameters $a$ and $b$ with $1\le a<q$ and $0\le b<q$, giving
$$x\mapsto f_{(p,a,b)}(x)=\min\Big(\big({(2^a)}^{x+b}\bmod p\big),\,p-\big({(2^a)}^{x+b}\bmod p\big)\Big)$$

With $p>2^{33}$, the function ${\tilde f}_{(p,a,b)}$ obtained by iterating that $f_{(p,a,b)}$ while the result is larger than $2^{32}$ is a permutation of the integers in $[1,2^{32}]$.

And now $x\mapsto h_{(p,a,b)}(x)={\tilde f}_{(p,a,b)}(x+1)-1$ defines a permutation $h_{(p,a,b)}$ of the 32-bit integers, as desired, which is considerably easier to evaluate in the forward direction than it is to invert.

As an illustration, for $p=\lceil2^{32}\pi\rceil+3062=13493040767$, $a=1$, $b=42$, it is easy to compute $h_{(p,a,b)}(4)=2511267353$ (because $f_{(p,a,b)}(5)=5073155518>2^{32}$, $f_{(p,a,b)}(5073155518)=5723706427>2^{32}$, $f_{(p,a,b)}(5723706427)=2511267354\le2^{32}$). But it is sizably more difficult to solve $h_{(p,a,b)}(x)=2919107273$ for $x$. Try it!

I guesstimate that inversion for one output is several hundreds times harder than direct computation even using sophisticated algorithms to solve the DLP (index calculus or NFS); thousands times harder with simpler algorithms (BSGS or Pollard's ρ); and hundreds thousands times harder by brute force.

In a white box context, it might be slightly better to have the implementation contain $2^a\bmod p=g$ rather than $a$, and implement ${(2^a)}^{x+b}\bmod p$ as $g^{x+b}\bmod p$ or $g^{(x+b)\bmod q}\bmod p$. On the other hand, in a black box context, the forward implementation can implement ${(2^a)}^{x+b}\bmod p$ as $2^{(a\,x+b)\bmod q}\bmod p$, which allows a slightly faster evaluation.

The number of iterations of $f_{(p,a,b)}$ is about $p/2^{33}$ on average, and for $p<2^{34}$ is more than $k$ with probability less than about $2^{-k}$. In order to slow down evaluation (and reversal), we can chain several $h_{(p,a,b)}$ using different $p$, which is better that an overlarge $p$ on two accounts: the evaluation time tends to depend less on $x$; and attacks making heavy pre-computations to later efficiently solve multiple discrete logarithm problem in the same $\Bbb Z_p^*$ are thwarted.

There seems to be better constructions (in the sense of making the ratio of reverse to forward cost higher) using the DLP on a super-singular elliptic curve; see this and its comments, and perhaps this for the curve.


A one way Function provably reversible at N applications with the same seed? I'm looking for a function that is generally one way from some secret $F(s, A) \rightarrow Y$, where $A$ is known, $Y$ is produced (also known), and $s$ is kept secret. But whose repeated application results in the function being reversible (to determine $s$) at some step $F_n$.

Edit: $A[1,2 \dots n]$ is a set of numbers not known in advance (prior to each successive application of $F$), but of a particular type, say the first 16 bytes of a SHA-256.

It is essential that it can be proven that the function is not reversible at $n-1$ (or that the work necessary to reverse at $n-1$ is very high) and sufficiently easy to reverse at $n$ ($n+1$ etc.), and that this is provable for any s belonging to a certain group.

$F(s, A_1) \rightarrow Y_1\\
F(s, A_2) \rightarrow Y_2 \\
\dots \\
F(s, A_3) \rightarrow Y_n$

Would greatly appreciate a pointer in the right direction (what functions to look at, or even some reading on the subject), thanks.

F(s,A) can be

a prefix-free encoding of the number of elements in the finite field encoded by s

|| $\:$ the polynomial R (as described at this link) from that finite field $\;$ ||

the output of the degree-at-most-(N-1) polynomial encoded by s over that finite field at the point A

.
Let SP be the set of polynomials of degree at most N-1 over the finite field. $\:$ N input-output pairs would allow one to efficiently find the encoded element of SP by Lagrange interpolation. $\:$ Observe that for any given field, for all A, evaluate-at-A is a linear map from SP to the field. $\:$ Since Lagrange interpolation will always give a compatible polynomial (and not just find one when there is one), that linear map is surjective. $\:$ Thus, for all integers x in {0,1,2,3,...,N-2,N-1}, for any
given N-x input-output pairs and any given z other inputs, the outputs at those x inputs for such a polynomial chosen uniformly from the subset of SP that produces the given N-x input-output pairs are independent and uniformly distributed. $\:$ Observe that any guess at s can only be correct if it gets those outputs correct.

Therefore, for all integers x in {0,1,2,3,...,N-2,N-1}, the probability of guessing s correctly is

at most [[the sampling error for SP] plus [one over [[the number of elements in the field] to the x]]].

This wiki article describes how to do arithmetic over finite fields given an irreducible polynomial over

their characteristic field. $\:$ This paper gives the "simplest" such polynomials for degree at most 10000

over the field with 2 elements, and these two papers give algorithms which can let you confirm that

those polynomials are in fact irreducible (confirming that they're the simplest would be harder).

More generally, over small prime fields, this paper gives a deterministic algorithm

for constructing irreducible polynomials and this paper gives constructions that

are presumably more efficient for degrees divisible by a not-too-small power of 2.


Choosing between different Gaussian Sampling algorithms? Is the gaussian sampling described in the original paper (https://eprint.iacr.org/2013/383.pdf) faster (samples/sec) than the Knuth Yao sampling.
As far as I know KY sampler is the fastest discrete gaussian sampler.
I found one survey here https://www.sav.sk/journals/uploads/0212094402follat.pdf. It mentions both of these algorithms but without any comparative analysis.

KY is indeed the faster than the method you referenced. However, it also uses a lot of memory (it needs to store a little more than the probabilities of each possible output in high precision). Depending on the available memory and the width of the distribution you are trying to sample from,  this can be prohibitively large, especially when implementing it on a constrained device. This is what the paper by Ducas et al. addresses: their method is relatively fast (much faster than rejection sampling, but not as fast as KY) and uses much less memory. In essence, it simply gives you a different time-memory trade-off.


Can I work around these padding issue in AES 256 ECB due to Reed solomon encoding? Disclaimer: I do NOT believe AES-ECB to be at all useful for encryption. That said, due to time and bureaucratic issues that I'm not in control of, I need to use AES-ECB.

I get packets of data that are Reed Solomon encoded. Each reed solomon encoded packet has length 255 bytes. On decoding, I get the message which is 223 bytes. (This is RS(255,223) with 8-bit symbols. Each codeword contains 255 code word bytes, of which 223 bytes are data and 32 bytes are parity).

I must now encrypt this data (223 bytes) and then RS encode it again to get back a packet of 255 bytes. However, when using AES ECB in block cipher mode, a byte of zeroes has to be padded in before encryption.

This padding yields a ciphertext that is 224 bytes long. This can't be RS encoded as the packet is required to be 223 bytes.

I realize that hoping this can be solved with a block cipher might be impossible, but any help or workarounds would be really appreciated!

You can use ciphertext stealing as the padding mode and the length won't be increased, see: ECB ciphertext stealing .


Is it true for Java that the transformation mode and padding is ignored when using RSA? Consider GregS's comment to this question (more specific to bouncycastle's provider implementation):

https://stackoverflow.com/questions/11717646/bouncycastle-rsa-key-size-and-padding

  The mode, ECB in this case, is ignored for RSA.Use PKCSPadding. The
  max amount of data you can encrypt is the size of the modulus in bytes
  minus 11.

I've read several articles that seem to state similar views, including this one:

http://armoredbarista.blogspot.com/2012/09/rsaecb-how-block-operation-modes-and.html

Although that article appears to make the case that it is only ignored when the data exceeds the size of the moduli.

Basically I have a small amount of data to encrypt (a username and password), a private key with a 2048 bit key length, and I'm using the RSA/ECB/PKCS1Padding cipher transformation for encryption. Is this considered "textbook" or "plain" RSA in Java?

I believe I am using a secure approach for our needs, but I need to be sure.

ECB, CBC and such cipher modes are something that relate to symmetric cryptography.
In context of RSA, it is important to study from documentation of the product what they mean as they do not ordinarily apply.

Based on the articles you provide, this statement is correct:

  The mode, ECB in this case, is ignored for RSA.Use PKCSPadding. The max amount of data you can encrypt is the size of the modulus in bytes minus 11.

PKCS#1 standard defines many padding schemes. The more elaborate and less ambiguous name for this scheme and padding is RSAES-PKCS1-v1_5. You just need to ensure that the data you intent to encrypt is at most 245 bytes.

It is common to warn against using textbook RSA. This warning practically means "do not use RSA without using a padding scheme". Thus, RSA with any padding from PKCS#1 is not textbook RSA.

Secure?

In most protocols, what is encrypted with RSA with PKCS#1 padding is a secret key.    Encrypting username and password is significantly less common occurrence. Using RSAES-PKCS1-v1_5 securely needs some care in the application. Long story short, it is possible that this padding scheme would not meet the needs of this use. However, as I don't know the context and other algorithms applied, I cannot know if this is secure or not in this context.

The intent of RSA encryption is to ensure that decryption is only performed by party that has access to the private key. RSA encryption does not authenticate the sender, anybody may send a message which appears correct as far as RSA and the padding scheme is concerned.

If sender authentication is needed (quite common), it is necessary to use a digital signature scheme, such as RSASSA-PKCS1-v1_5 in conjuction with the encryption algorithm.

There is a newer padding scheme (Optimal Asymmetric Encryption Padding), which addresses some of the outcomings of RSAES-PKCS1-v1_5. However, as a general advice, I would recommend trying to find a security protocol, which'll implement the entire security use case you have. Implementing any practical security protocol from small blocks like this RSA/ECB/PKCS1Padding is tedious and unfortunately error prone.


How to solve cipher encrypted with Vigenère + Columnar Transposition? Vigenère's weakness is Kasiski's test and index of coincidence. However, if you put columnar transposition on top of Vigenère, that weakness is gone. The text is now shuffled and you can't search for digrams/trigrams, because they will give you wrong key length pattern.

You also can't solve Columnar Transposition. For example, you try key length $i$ and you put the text in $i$ columns. Normal Columnar Transposition is solved by matching columns with each other and counting how good the match is (compared to English text digrams). The best match is then the correct column order. But because the text is encrypted with Vigenère and letters are substituted, you won't get correct result.

Is such a cipher considered very good / unbreakable or how does one attack it?

Obviously such a combination of ciphers is stronger than any of these two ciphers alone.

The Vigenere cipher provides "confusion", while the transposition cipher provides "diffusion". These are terms used by C. Shannon, refer to http://en.wikipedia.org/wiki/Confusion_and_diffusion.

Modern ciphers like AES are making use of diffusion and confusion as well. But - besides additional other operations - here several rounds are applied.

I think applying these two encryption methods (vigenere & transposition) to a plain text only once will still be a rather weak encryption (at least compared to AES).

In the following I provide some of my thoughts. I haven't verified them, so I cannot guarantee that everything described below works as expected. :-)

Some thoughts of how to attack such an encryption: Evolutionary algorithms (http://en.wikipedia.org/wiki/Evolutionary_algorithm) are one way to break transposition ciphers (btw, EAs can be used to break Vigenere ciphers as well). One variant of such an algorithm is called genetic algorithm (http://en.wikipedia.org/wiki/Genetic_algorithm). Investigations in this area have been done, e.g. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.4358&rep=rep1&type=pdf.

One main function within a genetic algorithm (GA) is called fitness function. Once a key has been chosen the given cipher text is decrypted using this key and the resulting clear text is passed to the fitness function (http://en.wikipedia.org/wiki/Fitness_function). The fitness function returns a measure how close the result comes to an optimum solution.

In case simple transposition ciphers are to be solved the fitness function determines how close the clear text comes to the English language.

Now if a clear text is encrypted by the Vigenere cipher, and the resulting Vigenere cipher text is encrypted using the transposition cipher then the resulting cipher text can be attacked by treating it as a "simple" transposition cipher. The difference is now that the fitness function must return a measure how probable it is that the resulting clear text is a Vigenere cipher.

Vigenere ciphers have certain characteristics, e.g. an autocorrelation will show periodic maxima (http://www.cryptool-online.org/index.php?option=com_content&view=article&id=90&Itemid=107&lang=en). Thus it should not be a problem writing a fitness function which distinguishes a Vigenere cipher from a random sequence of characters.

Once the transposition cipher is solved solving the Vigenere cipher is rather straight forward.

Implementing a fitness function checking for the Vigenere cipher will probably be slower than a corresponding function checking for English text. Thus I expect that breaking the cipher "Vigenere & transposition" will require much more processing time than breaking any of these ciphers alone.

There is still an open question: How to find the key length for the transposition cipher? One possible way might be to apply an autocorrelation to the cipher text. I would expect to see maxima at multiples of the least common multiple of the Vigenere key length and the transposition key length. This should at least limit the potential key lengths to try.


Prime fields vs non-prime fields I was watching this class about AES in this LINK and I was trying to grasp the concept of prime fields, which is a finite field with prime order $p$.

The non-prime field part (order is $p^n$) is where it gets harder for me. The teacher jumps into "extension fields", and does not explain the link between it and non-prime fields. Also, he just affirms that elements of $GF(p)$ are integers, while elements of $GF(p^n)$ are polynomials.

Why the difference between the two?

elements of $GF(p)$ are integers, while elements of $GF(p^n)$ are polynomials.Why the difference?

TL;DR: because integers modulo $p^n$ do not form a field.

Here's a pragmatic construction of $GF(p^n)$ useful for applied cryptography, including AES which uses the field $GF(2^8)$ extensively.

$GF(p)$ for prime $p$ is the field of arithmetic modulo $m$ for modulus $m=p$. Arithmetic modulo an integer $m$ works as integer arithmetic except that all results are reduced to the range $[0,m)$ by subtraction of $q\,m$ for some appropriate integer $q$. Arithmetic modulo $m$ keeps the usual properties of addition and multiplication: their are internal laws with associativity, commutativity, distributivity, neutral $0$ for addition and $1$ for multiplication, existence of an opposite (w.r.t. addition) for all elements. And, specifically when $m$ is prime, arithmetic modulo $m$ gains a property of rationals and reals that integers do not have: existence of an inverse/reciprocal (w.r.t. multiplication) for all elements except $0$. That additional property makes arithmetic modulo $p$ a field of $p$ elements, when arithmetic modulo a composite $m$ is not¹.

When we want to make a field of $m$ elements and $m$ is not prime, we thus can't use arithmetic modulo $m$. It turns out that there is an alternative construction if and only if $m$ is of the form $p^n$ with $p$ prime. That's $GF(p^n)$.

One way to think an element $A$ of $GF(p^n)$ is as a vector $(a_0,a_1,\ldots,a_{n-1})$ of $n$ elements $a_i\in GF(p)$. At least that gives us the right count of elements $p^n$, and we can define a well-behaved addition as
$$A+B=(a_0+b_0\bmod p,a_1+b_1\bmod p,\ldots,a_{n-1}+b_{n-1}\bmod p)$$
with the all-zero vector the neutral. But somewhat we need to define multiplication in such a way that $A\,B$ is also a vector of $n$ elements in $GF(p)$, and all except one elements have an inverse².

That's where polynomials come to the rescue. We assimilate $A=(a_0,a_1,\ldots,a_{n-1})$ to the (univariate) polynomial $a_0+a_1\,x^1+\ldots+a_{n-1}\,x^{n-1}$ of degree less than $n$ and coefficients $a_i\in GF(p)$. Notice that the rules of addition of polynomials with coefficients in $GF(p)$ coincide with our earlier definition of addition.

Now we pick a polynomial $M=m_0+m_1\,x^1+\ldots+m_{n-1}\,x^{n-1}+m_n\,x^n$ of degree³ $n$ with coefficients $m_i\in GF(p)$, and define the product $A\,B$ in our would-be field as
$$\underbrace{A\,B}_{\text{in would-be field}}=C=\underbrace{A\,B\bmod M}_{{\text{in polynomials with}\\\text{coefficients in }GF(p)}}$$
The right side means that $C$ is the⁴ polynomial with coefficients $c_i\in GF(p)$, of degree less than the degree of $M$ (hence of degree less than $n$, hence representable as a vector of $n$ elements in $GF(p)$ as desired), such that there exists a polynomial $Q$ with coefficients $q_i\in GF(p)$ with
$$0=C+Q\,M-A\,B$$
per the normal rules of addition and multiplication of polynomials with coefficients in $GF(p)$. That is
$$0=\sum_{0\le i<n}\left(\left(c_i+\sum_{0\le j<n}\left(q_j\,m_{i-j}-a_j\,b_{i-j}\right)\right)x^i\right)$$
or equivalently when we get back to vector notation rather than polynomials
$$\forall i\in[0,n),\ \underbrace{0=c_i+\sum_{0\le j<n}\left(q_j\,m_{i-j}-a_j\,b_{i-j}\right)}_{\text{in }GF(p)\text{, that is}\pmod p}$$
We've already seen that this construction of multiplication is an internal law. It's easy to show that it inherits from the field of arithmetic in polynomials with coefficients in $GF(p)$ the properties of associativity, commutativity, distributivity, and neutral the constant polynomial $1$, that is the vector $(1,0,\ldots,0)$. We have constructed a commutative ring with $p^n$ elements.

It can be shown that if (and only if) polynomial $M$ is irreducible, each element has an inverse, which completes the field properties. And it can be shown that there exits an isomorphism among the different fields that we obtain for different irreducible polynomials $M$, which is why mathematicians speak of the field $GF(p^n)$, rather than of the field $GF(p^n)$ obtained for a particular irreducible polynomial $M$, as practical cryptographers often do.

  Relation between extension fields and non-prime fields

A field $G$ is an extension field of $F$ when $F$ (or $F'$ with a trivial mapping to $F$) is a subset of $G$ and is a field under the same addition and multiplication laws that make $G$ a field.

When we restrict $GF(p^n)$ constructed as above to the set of constant polynomials (equivalently, the set of vectors of $n$ elements in $GF(p)$ with all expect the first set to zero), we are back to a subset of $p$ elements that matches $GF(p)$.

Otherwise said, $GF(p^n)$ is an extension field of $GF(p)$.

Notes:

¹ Arithmetic modulo a composite $m$ is only a commutative ring of $m$ elements, but not a field. Proof: if $m$ is composite, let $a$ be the smallest prime divisor of $m$. If $a$ had an inverse $x$ modulo $m$, we'd have $a\,x\equiv1\pmod m$, that is $\exists q\in\Bbb Z,\ a\,x=1+q\,m$. We can write $m=a\,b$ for some $b\in\Bbb Z$. Hence $a\,x=1+q\,a\,b$, hence $a\,(x-q\,b)=1$ in the ring of integers, which can't be since $a$ is prime. Hence $a$ has no inverse modulo $m$ when $m$ is composite. Since $a$ is not zero, one of the field requirement is not met.

² That's the hard part. In particular, the construction of the product as $A\,B=(a_0\,b_0\bmod p,a_1\,b_1\bmod p,\ldots,a_{n-1}\,b_{n-1}\bmod p)$ leaves multiple $A$ without an inverse: all those with at least one of their $a_i=0$ in $GF(p)$.

³ That's exactly degree $n$, otherwise said $m_n\ne0$ in $GF(p)$.

⁴ The polynomial $C=A\,B\bmod M$ is uniquely defined by the relation $0=C+Q\,M-A\,B$. That $C$ can be (and in practice often is) obtained by computing the product $A\,B$ as a polynomial with coefficients in $GF(p)$ of degree less than $2\,n-1$, and progressively reducing that product's degree from at most $n+j$ to less than $n+j$, by computing $q_j$ and subtracting $q_j\,x^j\,M$, with $q_j=d_{n+j}/m_n$ computed in $GF(p^n)$, and $d_{n+j}$ is the high-order coefficient of the progressively reduced product. To simplify that computation, it is customarily used $m_n=1$, that is $M$ a monic polynomial.


What type of groups does Microsoft's U-Prove use (Schnorr... etc?) I'm trying to learn more about the Subgroups implementation of Microsoft UProve.   I'm unsure if they are Schnorr Groups or use a different foundation?

Can anyone point me to the technical reading required to understand the implementation?  (anything appropriate for a determined, yet fledgling novice would be appreciated)

U-Prove Recommended Parameters describes the groups used by U-Prove.

For the subgroup variant it references Appendix A.1.1.3 of FIPS186-3 which is about groups for finite-field based DSA. AFAIK these groups are Schnorr groups, even though NIST never refers to them as such.

The ECC variant uses standard NIST curves such as P-256, P-384 and P-521.


Recover from compromised shares with Shamir Secret Sharing He is a quote from Wikipedia page for Secret Sharing:

  If the players store their shares on insecure computer servers, an attacker could crack in and steal the shares. If it is not practical to change the secret, the uncompromised (Shamir-style) shares can be renewed. The dealer generates a new random polynomial with constant term zero and calculates for each remaining player a new ordered pair, where the x-coordinates of the old and new pairs are the same. Each player then adds the old and new y-coordinates to each other and keeps the result as the new y-coordinate of the secret.

The idea here is that if you add a polynomial with constant term $0$ to another polynominal, it doesn't change the constant term. But I don't get how this is better than just redistributing new shares.

If you distribute the updates over an insecure channel, then the attacker can intercept them, steal new shares and convert them to old shares by substracting the update. So you have to distribute the updates over a channel as secure as the one originally used to distribute shares. So what's the point of using updates instead of just generating new shares?

The point is that the dealer generating the update needn't know what the shared secret is.

If we had a dealer that remembered what the shared secret was (or we asked enough people to contribute their shares so that the dealer could reconstruct it), then yes, the dealer could generate new shares.

However, this would require is a dealer that did know the secret. In contrast, anyone can generate a random polynomial with an constant term $0$; all they would need is the degree of the polynomial (that is, the threshold of the secret sharing scheme), the field the polynomial is in, and the $x$ coordinates of the uncompromised parties; all this can be made public without compromising the security of the system.

Remember, the whole point of the shared secret scheme was that no one knows what the secret is (until it's officially time to reconstruct it).


Problem in Identifying relevant documents to evaluate Precision in Information Retrieval (IR) Systems In searching engines, especially for ranked search approaches, How to evaluate the results returned by IR Systems . The precision is evaluated by the below equation:

(Number of relevant documents in retrieved documents)/(Number of retrieved documents).

However, how to decide which returned documents are relevant for the given query? For that, should we go through each returned document to find if it is relevant or not?  Or should we say if any returned document contains all the query keywords?

Yes, the client needs to figure out which of the results are actually relevant. For obfuscation reasons the server returns irrelevant documents and also cannot know which documents are irrelevant so the client has to make that distinction.


How can we define $\epsilon$-differential privacy for non-deterministic algorithms? We know that  non-trival deterministic algorithm does not guarantee privacy and randomization is essential for privacy (pp.16 in [Dwork and Roth 2014] ).  The well-known $\epsilon$-diferential privacy is defined for randomized (probabilistic) algorithm (see the link https://en.wikipedia.org/wiki/Differential_privacy).
From a broader perspective of uncertainty, I wonder whether we can define a similar diferential privacy notion for non-determinstic (multi-valued or set-valued) algorithms? And how?

I find that question very interesting. They are arguing that there is not a notion of diferential privacy for all non-deterministic algorithms. Some non-deterministic algorithms could be $(\varepsilon,\delta)$-differential private. But not every non-deterministic algorithm is $(\varepsilon,\delta)$-differential private, they give the example of the algorithm.
Algoritm:
Input: Database $D$
Output: $f(D)$ dropping a row/register from D (non-deterministically), where $f$ is the query function (median,sum,etc).
Note this algorithm is non-deterministic but it is possible to know all the information from the databases if you use this algorithm repetitively. Consider the worst case, the attacker knows all the database except one row (That's why is a condition that $|D-D'|\leq 1$). Therefore you can't guarantee privacy for all or some the rows/registers.


Is my id obfuscation algorithm secure? I'm designing an id obfuscation system.
My system includes:

Embedded chips, each chip has a unique 32-bit address (id).
Server
Insecure low-bandwidth unstable one-way channels from the chips to the server.

The chips send messages to the server over the insecure channel.
The messages are simple "I'm alive" notifications. There is no meaning to forging messages (no benefit to the attacker).
The server should be able to recover which chip sent which message. However, I don't want attackers to be able to trace specific chips for long period of times, i.e., the messages should not contain the chip's id, but an obfuscated id, which should change once in a while (in my case every ~5 minutes on average).
In my case, $2^{16}$ different obfuscated ids per chip are enough (the obfuscated ids will repeat every ~227 days).

One way to obfuscate the id is to encrypt the id together with a counter. For example, use a 48-bit block cipher to encrypt the concatenation of the 32-bit id with a 16-bit counter, that increases every ~5 minutes.
I don't know of any 48-bit block cipher, but 64-bit block-ciphers, such as Blowfish and Skipjack, can also be used: by encrypting the concatenation of the 32-bit id with a 16-bit counter and some fixed 16-bit value (could be zeros).

However, there are two more requirements:

The encryption secret key must not be saved on the chips - Some of them may fall into the wrong hands and be reverse-engineered.
Asymmetric encryption cannot be used ... They take too much time and create too large outputs (over 64-bit).

This means that all the obfuscated ids must be pre-calculated and saved on the chip. It also means that using a 64-bit block-cipher will consume 33% more space on the chip than a 48-bit block-cipher.

Since I don't know of any commonly used 48-bit block cipher, I had the following idea.
For each each, encrypt all concatenations of the 32-bit id with any 32-bit value.
Save on each chip only the results that end with 16 zero bits (obviously, without last 16 zero bits of each obfuscated id).
There should be around ${2^{32}}/{2^{16}}$ such obfuscated ids for each chip, which is exactly the amount I need.

The server will receive the 48 bit obfuscated id, pad it with 16 zero bits, decrypt, and slice the first 32-bits of the result to recover the chip's real id.

The only flaw is that the pre-calculation of the obfuscated ids for each chip is time consuming.

Can you see any flaws in my algorithm, besides that? Do you have any suggestions to improve it?

Another approach was to use 32-bit block ciphers (skip32), and call them several times so all the 48-bits are used. However, from what I learned, 32-bit block ciphers are considered obsolete.

Furthermore, if you have any suggestion that includes a stream cipher, please notice that the channels are unstable and messages may drop - CBC mode will not be recoverable on the server side. CTR mode that includes sending the counter is also problematic, because an attacker can trace a chip merely by watching the counter in the messages - if a message's counter is 123, and 5 minutes later I see a message with a counter of 124, it probably originated from the same chip (syncing all chips is not practical).

You are over-thinking about cryptography. It's not supposed to be that complex.
I started with the idea "let make 1 chip have multiple id".
And I come up with something relatively simple than what you mentioned so far. (I'm not sure if this usable in your situation or not. It's just based on the info you described.)

Prepare: I will make every chip have unique id and a counter like you mentioned.
Setup: When a chip is registered to the server I will make the server generate keyed hash using unique id as key and counter as message but instead of generate just 1 hash from the current value of counter let say I generate 5,000 consecutive hash start from the current value of counter and store generated hashes in the database.
Identify(chip): Instead of directly send the unique id to the server just send keyed hash with the same algorithm as hashes generated on the server then increase the counter in the chip.
Identify(server): The server can determine the chip id just by querying the database with received hash. (This operation should be very fast since hash value can be indexed.) From this querying the server should know the counter value inside the chip too not just the unique id. The server can now delete current and older hash from the database. If hashes in the database for a chip fall below (say) 2,000 the server will generate consecutive hash to fill 5,000 hash pool.
That's the overview. It's seem like I missed 64-bit communication chunk constrain. (Thanks to Ricky Demer for pointing it out.)
To address that issue: the hash used should no longer than 64-bit.
Just allow hash collision happen in the database we can simply don't use hash as the primary key.
When the chip send collision hash just ignore that and wait for the next sample. If the missing sample is significant in some way we can assume that next hash will have the same chip as the owner hence we can pin point which chip send the previous hash. (If it still undecidable just wait for next one.)
Or we can also assumed that the chip that just appear with the collision hash is not the one who send the hash.

This idea is derived from what you mentioned about the counter that leak chip identity in some way but now we use it on the server.
And that's it I will do it this way if no one point out any flaw in this approach (which I myself cant see).


Tamper-evident audit logs I want to be able to detect tampering in a log file that is under the control of an untrusted party. I am not interested in secrecy, only the integrity of the contents in the file - so I want to detect if entries have been removed/changed. The solution that I seem to have found from a short google search is to use hash chains linking the current log entry to all other previous entries. The untrusted party publishes the hashes with some acceptable frequency such that any tampering after the time of publishing can be detected. Is there any technique that will accomplish something similar without the need for publishing the hashes frequently?

The verifier and logger start with a seed for a forward-secure pseudo-random number generator.

To denote a valid ending of a log, append the string of the next $b$ bits of the PRNG's output

to the end of the log. $\;\;$ To add a log entry, get the next $\:b\hspace{-0.03 in}+\hspace{-0.03 in}k\:$ bits of the PRNG's output,

use the last $k$ of those bits to mac the new content, append the concatenation of the new

content with its mac to the log, and then erase those $\:b\hspace{-0.03 in}+\hspace{-0.03 in}k\:$ bits and the previous PRNG state.

This allows you to replace "The untrusted party publishes the hashes"

with "The untrusted party erases the old PRNG state".


Trapdoor committement using ring lattices involving three parties Assume there are three parties say A, B, C.

A commits to a message $m$ say $c(m)$ and sends tuple $(m,c(m))$ to B.
B has to prove to C that he possesses commitment $c(m)$. There is no interaction between A and C. But B should not cheat by sending commitment to some other message $m^\prime$.

I guess for this we need A to generate $c(m)$ using his own trapdoor and later C can verify it is generated by A itself. Is it possible to achieve this using lattice based hard problems like $RSIS$ or $RLWE$.
Or is there any other way to achieve this using $RSIS$ or $RLWE$. ?

I think that this is just a digital signature scheme. $A$ should generate a private signing key and a public verification key for your signature scheme of choice. The then create a signature for the message $m$ and which you are calling the commitment $c(m)$. $B$ can then pass on the $c(m)$ to $C$ who can confirm that is is signed by $A$, but $B$ cannot produce signatures for other messages that verify using $A$'s verification key.
There are several lattice-based signature schemes though they are all quite tricky to parameterise and implement securely. The NIST competition has advanced the lattice-based signatures FALCON and Crystals DILITHIUM to the final round.


Why is RSA unsafe if N=pq can be factored? I just started learning about cryptography and specifically RSA, and the texts I have read don't have a proof or explanation for why RSA is unsafe if you can factor N=pq, it merely asserted this. Is there a formal reason for this?
Thank you in advance :)

Let's assume RSA works.
There is a person, who created the key. He chooses 2 primes, multiplied them, and publishes the modulus with another number he can choose almost freely (it has to be coprime to $(p-1)(q-1)$).
So if you give the attackers the factorization, what else is there, that the attackers does not know? There isn't anything.
There is not much to put formally. If the attackers knows all secret information, there can not be any security. What should it be based on? Unless we allow security to be based on magic fairy dust.


Compression function is not collision resistant but Merkle-Damgard is collision resistant Is it possible that you can still have a collision resistance in Merkle-Damgard even if the compression function has a collision?

Yes, a hash built per the Merkle-Damgård construction can be collision-resistant even if its  compression function has a known collision.

Consider SHA-256. Note its round function $F:\{0,1\}^{256}\times\{0,1\}^{512}\to\{0,1\}^{256}$ where the first argument is the state and the second is a message block. Now define $F'$ identical to $F$, except that $F'(0^{256},0^{512})$ is defined to be $F(0^{256},1^{512})$.

$F'$ has a known collision, yet the variant of SHA-256 using $F'$ is collision resistant, because we can't find a way to bring the state of SHA-256 to all-zero, which would essentially be a preimage attack.


Limiting how many key pairs someone can generate without compromising their keys Is there any way to assign someone a limited quota for how many cryptographic key pairs they can generate (ECC, RSA, any algorithm), and preferably non-interactively? By non-interactively I mean there is no multiple handshake or multiple round trips between me and the person doing the generating and the relationship could perhaps be anonymous.

I'm imagining something where I generate, say, 50 tokens/certificates/whatevers and give them to someone. That person is then able to generate 50 key pairs and I am able to test to ensure that those 50 key pairs were properly entitled.

Of course the person could generate more key pairs without using my entitlements, but those would not check out.

I have a sense that something like this could be possible with homomorphic encryption or zero knowledge proofs or something similar but I can't think of a way to do it.

Anybody can run any of the usual generators for asymmetric primitives as many times as they want. And they can do this without compromising the security of the private key. Generally the trust of a key pair by a user is however not in the private key, but in the public key or certificate around the public key.

Now you could embed a signed token in the certificate, but in that case you must make sure that the token cannot be reused. This could for instance be managed by a trusted third party, such as a Certificate Authority. You could for instance create a certificate extension and require a CA to validate that the token isn't reused. You then have another party to hold responsible if a duplicate token is ever found.

What you cannot do in this digital world is avoiding duplication. This can only be managed if you somehow manage to secure the processing of the data. For more information on that you'd have to look at digital rights management (DRM) rather than homomorphic encryption or zero-knowledge proofs - if you ask me.

And while I generally try and refrain from using buzz, this might be  a case where blockchain technology could actually be helpful in case you don't want to use a CA / centralized management.


Deduce modulus N from public exponent and encrypted data This is an RSA question, given data encrypted with a public key from an unknown RSA certificate of 2048 bit, let $X$ be the encrypted data, $M$ the unencrypted data, $c$ the public exponent and $N$ it's modulus. Knowing $X$, $M$ and $c$, can you deduce $N$?

$$
X = M^c \mod N
$$

You can have as many $M$ and corresponding $X$ as you want, hence:

$$
X_1 = M_1^c \mod N \\
X_2 = M_2^c \mod N \\
\dots
$$

I want to know if this is possible, mathematically and programatically. A brute force won't work here. Any ideas?

Given a message $M$, define the corresponding RSA ciphertext as $C = M^e \bmod N$.  We assume that the value of $N$ is kept secret.  However, the attacker is given oracle access to the encryption: on input a chosen message $M$, the attacker gets backs $C = M^e \bmod N$.

Question: How is possible for an attacker to recover the value of $N$?

Easy case (small exponent) Suppose the exponent $e$ is small (e.g., $e=3$) and known to the attacker.  Then, as detailed by yyyyyyy, given two ciphertexts $C_1 = M_1^e \bmod N$ and $C_2 = M_2^e \bmod N$, the value of $N$ can be obtained from $\gcd(M_1^e - C_1, M_2^e - C_2)$.
General case  Consider now the case where $e$ is large.  The attacker chooses two messages $M_1$ and $M_2$ and forms the messages $M_1' = M_1^2$ and $M_2' = M_2^2$.  The attacker asks for the corresponding ciphertexts and gets $C_i = M_i^e \bmod N$ and $C_i' = M_i'^e \bmod N$(for $i \in \{1,2\}$).  Since $M_1' = M_1^2$, it follows that $C_1' \equiv C_1^2 \pmod N$ and thus $(C_1^2 - C_1')$ is a multiple of $N$.  Similarly, $(C_2^2 - C_2')$ is a multiple of $N$.  As a consequence, $N$ can be recovered from $\gcd(C_1^2 - C_1', C_2^2 - C_2')$.

Remark 1  Note that the attacker does not need to know the value of $e$ to mount the second attack (general case).

Remark 2 Define $\tilde{N} := \gcd(C_1^2 - C_1', C_2^2 - C_2')$.
It might be the case that $\tilde{N}$ is not exactly equal to $N$.  The above description only implies that $\tilde{N}$ is a multiple of $N$.  However, knowing that $N$ is the product of large primes, it can be recovered from $\tilde{N}$ by removing extra small factors.  Yet, another option is to choose more messages and compute $N$ from $\gcd(C_1^2 - C_1', C_2^2 - C_2', C_3^2 - C_3', \dots)$.

Remark 3  There are several possible variants for the second attack.


Exponentiating big numbers for RSA operation I am following the book "Network security private communication in a public world - 2nd edition. Section 6.3.4.1 Exponentiating big numbers.

base = 123, exponent = 54, mod = 678

What I understand is that, first I need to convert 54 into binary, i.e. 110110. Then I should do (base^exponent)%mod only at those exponent where the exponent bits are set. For example:

123^2 = 123 * 123 = 15129 % 678 = 213

123^4 = (123^2)*(123^2) = (213^2) mod 678 = 621

123^16 = (123^4)(123^4)(123^4)*(123^4) = (621*621*621*621) mod 678 = 219

123^32 = (123^16)*(123^16) mod 678 = 501

If I do this, I am not getting the right answer which is (87). Can someone point out my mistake and help me understand the scenario.

The basic algorithm is square and optionally multiply.
start with 1 as your accumulator and then for each bit of exponent from MSB to LSB you square your result and if the bit is set multiply by base and appy modulus after each operation.
For any leading zeros you are just squaring 1 which doesn't do anything, just like we want. Then after the first set bit you get your base. After a 10 for example you get your base squared and so forth.

Edit: following fgrieu's comment I will add a second Right to Left method.
When looking at the exponent in binary we see it is the sum of powers of 2, and the result of the exponentiation is the product of the exponent by these powers. The resulting algorithm is:

Initialize acc=1, power=base //123
For each bit b from right to left do:

2.1. If bit is set: acc = acc * power % mod

2.2. power = power * power % mod

result is in acc


Is there any additively homomorphic schemes that can make range proof? I want to know whether there is any additively homomorphic schemes that can make a non-interactive range proof.

For example, I have a pair of public and private key pairs $(K_p,K_v)$ that satisfying a additively homomorphic schemes $E$, and I want to prove that the plaintext of $C=E_{K_p}(m)$ belongs to $[a,b]$, where $m, a$ and $b$ are both positive numbers. Is there any additively homomorphic schemes and non-interactive range proof scheme that I can use to prove the plaintext inside $C$ belongs to $[a,b]$.

Yes, you can use Paillier encryption as the homomorphic encryption scheme, and prove the encrypted plaintext falls within a range.

An interactive protocol can be found in Appendix A of this paper: Fast Secure Two-Party ECDSA Signing, by Yehuda Lindell, Crypto 2017.

A non-interactive protocol can be found in this paper: Non-interactive Zero-Knowledge Arguments for Voting, by Jens Groth, ACNS 2005.