Is there any vulnerability if I hmac(key,key)? It is a general question, but I'm using SHA-2.

My reason is to take a short pin or string and to generate a longer hash of that pin to locally generate a local key for personal use to be used to generate other passwords based on a domain and user name.

Eg.

Site password = Hmac( Hmac(pin,pin), Domain + username)

Or

Site password = Hmac( Hmac(pin,pin), hmac(Domain + username))

Additional info: Random passwords, unique for each account is ideal. But then I need to trust a password manager and install it on every device I own or use - this seems worse as I already trust Chromium/Google to store my passwords - why introduce another party? - and it seems popular password managers are patching design and implementation flaws a few times a year (and my code is no different).

My aim is to make any released passwords or hashes so long and pattern-free that my hashed passwords would remain un-cracked. And if cracked, then only one account would be compromised.

This is the idea I'm working on, it is not my idea, just my implementation.

In doing so I wondered if hmac(key,key) leaked info about the key or perhaps was trivial to crack. So after finding nothing on first page of a google search I decided to ask the SE community.

This is all useless.

The point of hashing passwords is to prevent a hacker who obtained the database with the hash to retrieve the original password.

With a short pin (assuming 4 digits) a hacker will simply calculate your hmac for all 10000 possible codes. None of your variations will make any significant difference.
A secure hash will hardly help either.


Is AES really used for Top Secret stuff? I've read almost everywhere that AES-256 can be used for Top Secret material (in the US). Is it really used or is it some kind of decoy to hide the more advanced algorithm they might use ?

Decoy for whom?

Security, and cryptography specifically, has a need for public scrutiny. It's been proven time and time again that hiding the nature of the protocol/algorithm/scheme doesn't provide any tangible security. Kerckhoffs' principle explains this:  A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.

It's "secure" up until someone finds out how it works and breaks it. Publically reviewed algorithms are something that people are always trying to break. The more people that try (and fail) to break something, the better that something is. This is important because it's really difficult to design crypto properly.

To answer your question specifically: Yes, AES is used for classified materials. Other algorithms are also used depending on the nature and use of the data.

A quick Google search came back with this PDF doc from NIST: Guideline for Implementing Cryptography In the Federal Government.  It may be out of date, or there may be better documents, but it's an enlightening read.


Key derivation design to avoid key leaks I have the first function that generates keys from AES decryption (128-bit key). It takes seed as input:

derived_key_1 = AES-DEC(key, seed)

seed and key are both fixed values that the attacker cannot changed. Attacker knows the value of seed. His first goal is to get derived_key_1.

He dooes have an extra capability. He has access to another function defined as follows:

temp_key = AES-DEC(key, chosen_seed)
derived_key_2 = AES-DEC(temp_key, seed)

where chosen_seed is controlled by the attacker. He can observed derived_key_2.

Assume the AES is implemented in hardware and AES primitive itself does not have timing side channel. Also attacker does not have other physical side channel (e.g., power, EM, fault, etc.) to observe other than timing of the two functions.

Are there any potential security concerns in this construction?

If there are problems, do the problems go away if I change the seed in the second function to seed_new which is still visible to the attacker, but not changeable by him.

I finally found out what you're asking for:

A specific (working?) related-key attack on AES!

For this answer I changed the notation a bit:

AES-DEC(K,P) got converted to $D_K(P)$
derived_key_X got converted to $DK_X$
seed (which is known) got converted to $S_K$
chosen_seed got converted to $S_C$
temp_key got converted to $K_T$

Now the answer:

AES by itself is immune to related key attacks to a great extent (there are some attacks but I think they require at least four related keys and I'd doubt the relations would be that complex).

So for an attacker to uncover $DK_1=D_K(S_K)$ he'd need to know $K$. There's no other way in doing this.
Now you're asking if knowing $DK_2=D_{D_K(S_C)}(S_K)$ does help. Let's de-construct this. An attacker can choose $S_C$ to be decrypted to $K_T=D_K(S_C)$, in order to learn $K_T$ he'd need to get K which is infeasible for AES. Now as the attacker has no chance to know $K_T$ there's the question left if $DK_2=D_{K_T}(S_K)$ does help him anyhow. He can't deduce $K_T$ from this equation as this would be a known-plaintext attack, which is infeasible on AES. The final question is if there're some strange relationships that may help the attacker in uncovering $K$ and hence $DK_1$.

No, he'd be (maybe) able to brute-force by trying out every possible $S_C$ until $K_T=D_K(S_C)=K$ which is extremely unlikely, as he could as well just brute force the normal key as he has no control over the value of $K_T$.

I hope this answers your question.


Alice trusts Bob only when Bob trusts Alice some story first: Alice and Bob both have public/private key pairs. Now Bob wants Alice to sign his public key id. Alice agrees but only when Bob signs the public key id of her.

Is this something that can be achieved? at the end, the signatures should only be valid or extractable if Alice and Bob did both made their signatures.

Is this something PGP supports? Is this somehow possible in general?

EDIT: There is a mthod of "Private Set Intersection". May by this can somehow applied to this case? Or maybe there is a similiar technique i currently not aware of.

This sounds like a fair exchange protocol where what is exchanged is a digital signature.
Per this paper, these are impossible without trusted third parties.

With a trusted third party, they are possible. Indeed people have proposed schemes that do what you describe again relying on a third party in the case of failure.


Is this modified Schnorr signature scheme secure? Signing

Let $y = g^x$, which is your public/private keypair.
Let $r = g^v$, for random $v$
Let $c = H(M)$
Let $z = (v + cx) \bmod q$
The signature is the pair $(r,z)$

Verifying

$g^z = ry^c \bmod p$

We further assume that the signer takes care not to sign the same message twice (that's his job in my application), and that the resulting malleability is not an issue. Is this scheme secure in the Random Oracle model?

If so, we can get trivially fast non-interactive multisignature aggregation.
https://crypto.stackexchange.com/questions/19291/need-fast-bulk-signature-verification-followed-by-fast-non-interactive-multisig

This scheme is insecure, as anyone with the public key can generate a forgery of an arbitrary message.

To do this, the forger would take the message $M$, the public key $y$, pick an arbitrary $z$, and compute $r = y^{-H(M)} g^{z} \bmod p$ and output $(r,z)$


State recovery of Micalli-Schnorr random number generator modulo a prime Let $p$ be a public prime of $n$ bits. Define the sequence $x_i=z_{i-1}^e \bmod p$, where $z_i$ is the $k$ high-order bits of $x_i$, and $r_i$ the remaining $n-k$ bits of $x_i$ (thus $z_i=\Big\lfloor\frac{x_i}{2^{n-k}}\Big\rfloor$ and $r_i=x_i\bmod2^{n-k}$).
Suppose $k>\max(2n/e, s)$, for some security parameter $s$ and $e$ is public with $\gcd(e,p-1)=1$.

I'm looking for an efficient algorithm to recover $x_0$ from the sequence $r_0, r_1, \ldots r_n$, or to predict remaining terms in the sequence.

EDIT: The answer below answers the RSA modulus case…

There is some related discussion in the answers to the Crypto.SE question “Why is the following RSA PRNG cryptographically secure?”.

Edit: As pointed out in comments, this answer is about the zRSA
The consensus among the answers seems to be that the required security assumption is too strong (strong RSA assumption) and the generator is too slow for practical use.

Here is a paper "On the Provable Security of an Efficient RSA-Based Pseudorandom Generator" by Steinfeld et. al. on this generator.

Let $N$ be the RSA modulus involved, $e$ the RSA public exponent, and $k$ the number of MSB bits taken from the generator at each iteration.

Basically  the authors suggest that under the strong RSA assumption it is possible to extract $$k= ((1/2)-(1/e))\log N$$  bits per iteration, without affecting the security.

And there is more recent work, behind a Springer paywall (see preprint here) "Time/Memory/Data Tradeoffs for Variants of the RSA Problem" by Fouque et. al. LNCS vol. 7936,
proposing Time/Memory/Data attacks on the generator, which for practical choices of the parameters is of course not a feasible attack. This latter paper also cites a paper by Hermann and May from ASIACRYPT 2009 in the introduction, where it has apparently been shown that if $$k\geq (1-(1/e))\log N$$ bits are extracted per iteration, the generator can be broken.


How do other, non-RSA algorithms, compare to the PKCS #1 standard? Arguably the PKCS suite of standards have a profit-oriented bias as they are promoted by RSA and promote their algorithms over others in the form of RFCs and other means.

I'm considering the possibility that this information bias may include disinformation or omission regarding substitute algorithms that may be equally good if not better.

  What are the other algorithms that could fill the space that that the PKCS#1 RSA algorithm  is currently holding?

RSA is two algorithms, one for asymmetric encryption, the other for digital signatures.

For asymmetric encryption, the main competitors of RSA would be:

The Rabin cryptosystem
ElGamal
NTRUEncrypt
Diffie-Hellman key exchange (in practice, key exchange is almost as good as asymmetric encryption, since most usages of asymmetric encryption are for sending a key, followed by symmetric encryption).
McEliece

For signatures, there are variants of the above; for ElGamal-like signatures, the most well-known variant is DSA.

The biggest advantage of RSA over almost any other competing algorithm is that it has a standard (PKCS#1) which unambiguously states where every byte should go. For wide industrial acceptance, such a standard is a must-have -- and it is even a free standard. This alone can explain the current dominant position of RSA. On that point, the only algorithms which can put up a fight with RSA are DSA, its elliptic-curve variant ECDSA, Diffie-Hellman, and elliptic-curve variant thereof. Only the DSA standard itself is free.

For performance, RSA public key operations are very fast, much faster than public key operations for discrete logarithm. On the other hand, elliptic-curve variants of DSA and DH are quite faster than RSA for private key operations. This can be seen by using OpenSSL with the openssl speed command-line tool. On a cheap and not-that-new 1.6 GHz AMD CPU (in 64-bit mode), I get this:

$ openssl speed rsa2048 dsa2048 ecdsap224 ecdhp224
Doing 2048 bit private rsa's for 10s: 1996 2048 bit private RSA's in 9.99s
Doing 2048 bit public rsa's for 10s: 70600 2048 bit public RSA's in 9.99s
Doing 2048 bit sign dsa's for 10s: 7311 2048 bit DSA signs in 9.99s
Doing 2048 bit verify dsa's for 10s: 6218 2048 bit DSA verify in 9.99s
Doing 224 bit sign ecdsa's for 10s: 43073 224 bit ECDSA signs in 10.00s
Doing 224 bit verify ecdsa's for 10s: 9760 224 bit ECDSA verify in 9.99s
Doing 224 bit  ecdh's for 10s: 11474 224-bit ECDH ops in 9.99s
OpenSSL 0.9.8k 25 Mar 2009
built on: Thu Feb 10 01:45:33 UTC 2011
options:bn(64,64) md2(int) rc4(ptr,char) des(idx,cisc,16,int) aes(partial) blowfish(ptr2)
compiler: cc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT
-DDSO_DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -DTERMIO -O3 -Wa,--noexecstack
-g -Wall -DMD32_REG_T=int -DOPENSSL_BN_ASM_MONT -DSHA1_ASM -DSHA256_ASM
-DSHA512_ASM -DMD5_ASM -DAES_ASM
available timing options: TIMES TIMEB HZ=100 [sysconf value]
timing function used: times
                              sign    verify    sign/s verify/s
rsa 2048 bits             0.005005s 0.000142s    199.8   7067.1
                              sign    verify    sign/s verify/s
dsa 2048 bits             0.001366s 0.001607s    731.8    622.4
                              sign    verify    sign/s verify/s
224 bit ecdsa (nistp224)  0.0002s   0.0010s     4307.3    977.0
                              op                 op/s
224 bit ecdh (nistp224)   0.0009s               1148.5

(I have slightly edited the output so that numbers are graphically aligned.)

This tests 2048-bit RSA vs 2048-bit DSA, and ECDSA and ECDH over a 224-bit curve, which should supposedly offer similar security. RSA is sorely beaten for private-key performance, but really shines for public-key operations.

Also (this is not apparent on this benchmark), DSA and ECDSA offer shorter signatures than RSA (56 bytes for ECDSA over P-224, vs 256 bytes for RSA-2048).

DSA and Diffie-Hellman got a lot of push from the US federal government in the last century, because at that time RSA was still patented. Otherwise, FIPS 186-3 would not have existed as a free standard. Nowadays, a lot of governmental organizations are pushing for the adoption of elliptic-curve cryptography, because it "feels unsafe" to rely on a single primitive: in case RSA gets spectacularly broken, there should be an alternate set of algorithms already developed.

For the figures above, we can see that ECDSA and ECDH are decent competitors for RSA, and have an edge over it in some specific cases. Yet support is not as widespread as for RSA, because the relevant standards are much more recent and involve higher-level mathematics (at some point, the implementer -- who writes the actual code -- must understand what is going on, and RSA is easier to understand).

In the future, NTRU may be a faster alternative, but right now it is aggressively patented, and still quite new (that's one of the benefits of a patent: it forces the rest of the world to wait a bit before deploying the algorithm, and this leaves time for cryptanalysts to do their job).


Does GCM (or GHASH) only provide 64-bit security against forgeries? In a recent comment a doubt was voiced about my answer, which claims GCM to requires $2^{128}$ for a successful forgery. The doubt was that the square root needs to be taken meaning the security would be $2^{64}$.

So of course I immediately checked the relevant security theorem (corollary 4):

$$\mathbf{Adv}^{\text{auth}}_{\operatorname{GCM}[\operatorname{Perm}(n),\tau]}(\mathcal A)\leq \frac{0.5(\sigma+q+q'+1)^2}{2^n}+\frac{q'(\ell_A+1)}{2^\tau}$$

with $\sigma$ being the total plaintext size in blocks, $q$ being the total number of encryption queries, $q'$ being the total number of decryption queries, $n$ being the size in bits of the underlying permutation, $\ell_A$ being maximum authenticated input length in blocks and $\tau$ being the tag size in bits.

Now clearly from this we can see that performing $2^{n/2}=2^{64}$ queries yields a strong enough advantage for a break.

Now my question is:
When talking about "n-bits of security" or "needs $2^n$ operations to break", do we usually talk about "online" security, ie queries to an oracle can be done and cost $1$ or "offline" security where no oracles are available or do we need to make this decision depending on the situation?

TL;DR: Does GCM offer 64 or 128 bit security?

According to the references, AES-GCM offers roughly 64-bit authenticity security (i.e., against forgery attacks) for 128-bit block size and long-enough (>=64-bit) tag size. When the number of queries appears in a security bound, "online" security should always be the case (for the bound items involving the number of queries). The word "query" corresponds to an oracle, which cannot be attacked offline.


Why does TLS 1.2 use GCM with additional SHA hash? I am studying the cipher suites provided by TLS 1.2 and found an interesting question.

TLS 1.2 adopts GCM for encryption and SHA256 or SHA384 for hash (e.g. TLS_RSA_WITH_AES_128_GCM_SHA256). But, GCM already provides data authenticity (integrity).

So, my question is that why TLS 1.2 includes another hash functions (SHA256 or SHA384) to provide integrity. Why not just use GCM for both encryption and hash, like IPsec?

Those ciphersuites do use GCM for both encryption and authentication. The hash function mentioned at the end is not used for integrity, but in the pseudorandom function. The TLS PRF is used to derive valid keys for the ciphersuite from the shared secret generated in the key exchange.


What is the smallest last value of sequence of integers from 1, where there is a collision in md5? Question is just out of interest.

If we take md5 hash from all integers from 1 to n, what is the first n, where its md5 collides with some previous md5?

Has anyone ever calculated and proved the smallest integer, where the collision occurs?

If not, is there considerations about md5 pseudo-randomness, which make probability of colliding md5-s higher for consecutive integers than for cryptographically random strings (birthday attack -> 2^64)?

This, for example, might be useful to know, when trying to hide real sequential order numbers.

MD5 has a 128-bit output, so it's expected that the first collision is around $2^{64}$. This is because of the Birthday-Problem in probability theory.

So you should be safe to take orders up to $$2^{64} = 18,446,744,073,709,551,616$$

But that shouldn't be a problem for you, because even though this number might not seem like a large number it actually is huge:

An Example:

If every human ($ \approx 7,000,000,000$ people) would place an order every second, then it would take $${2^{64} \over 7,000,000,000 * 3600 * 24 * 365} \approx 83.5$$ years.

So you can be extremely sure that you won't have a collision of hashed order-numbers.


Side-Channel Attacks in the Cloud Let's say we have some very sensitive personal files.  At all costs, we do not want any other pair of eyeballs to gaze upon them.  We need these sensitive files to be secure and available.
So, we have a bright idea: encrypt them and put them in the Cloud.
What side-channel attacks, if any, are specific to Cloud storage?
For example, could various Cloud-storage providers accidentally introduce weaknesses?

The cloud trend brought its problems. While in the classical system your servers were near to you, so the side-channel capability was limited. They were mostly on the smart-card systems where the card reader is malicious.
There are side-channel attacks on the cloud if the attacker can co-locate with you for this you need to use a shared machine to reduce your cost. Co-locating is a real problem since you are not selecting your cloud machine when you use shared hardware where virtualization happens.
Cache-Attack
Assume the attacker located you, so both you and the attacker use the same hardware. What they can do? Cache-attack on the AES encryption. This attack works if you encrypt your files on the server and use software AES (not AES-NI) that was using T tables for the encryption.
During your encryption the attacker runs their process, fills all of the cache lines, waits, your AES runs, and they enter again, then they check the cache lines. If a line still has attacker's data this implies the cache line is not used during the encryption, if changed then it is used during the encryption. Cache hit and cache miss. After many many steps, the key is extracted. How cache works see B degnan's answer.
Some articles;

2007 - ACI ICMEZ, O. Yet another microarchitectural attack: exploiting
I-Cache.

2012 - WEISS, M., HEINZ, B., AND STUMPF, F. A cache timing attack
on AES in virtualization environments

2016 - Ashokkumar C.; Ravi Prakash Giri; Bernard Menezes (2016). "Highly Efficient Algorithms for AES Key Retrieval in Cache Access Attacks"

2018 - Mehmet S. Inci; Berk Gulmezoglu; Gorka Irazoqui; Thomas Eisenbarth; Berk Sunar, Cache Attacks Enable Bulk Key Recovery on the Cloud

2018 - Gorka Irazoqui; Mehmet Sinan Inci; Thomas Eisenbarth; Berk Sunar Wait a minute! A fast, Cross-VM attack on AES

2018 - Yuval Yarom; Katrina Falkner, Flush+Reload: a High Resolution, Low Noise, L3 Cache Side-Channel Attack
.

Now the above works if you encrypt on the cloud and use software AES.
Deduplication
The aim was to eliminate copies of the data in the memory so that the cloud provider can reduce the cost, and we have another attack vector.

2011 - SUZAKI, K., IIJIMA, K., YAGI, T., AND ARTHO, C. Memory deduplication as a threat to the guest.

2015 - Gorka Irazoqui, Mehmet Sinan Inci, Thomas Eisenbarth, and Berk Sunar Know Thy Neighbor: Crypto Library Detection in Cloud. PoPETs 2015, 1 (2015)

2018 - Jens Lindemann and Mathias Fischer A Memory-Deduplication Side-Channel Attack to Detect Applications in Co-Resident Virtual Machines

This helps the attacker to determine whats is going on with the neighbors ( on the shared machine).
Spectre and Meltdown

Whereas Meltdown allows unauthorized applications to read from privileged memory to obtain sensitive data from processes running on the same cloud server, Spectre can allow malicious programs to induce a hypervisor to transmit the data to a guest system running on top of it.

Spectre is the thread to the shared hardware with hypervisor and patching the Spectre is not an easy job.
If you encrypt locally and use the cloud only as a storage service, then this means you don't process your data then you are fine from this attack.
But if you want the encryption on the server, this brings problems, you may be lost your encryption key. To mitigate this, some cloud providers provide HSM on the cloud those are useful mostly for servers and of course have some additional costs.
Encrypt locally, most CPUs have AES-NI so you have fast encryption locally. Use a password manager to manage your key and use a good password like dicewire for the master password.
The problem starts when you want to access your files. Dou you want to search on them then you need a mechanism. This is another long story. Start reading from the Song's famous article about this.
In any case, Fully-Homomorphic Encryption is the holy grail of Cryptography to solve many issues about the operation on the encrypted data. Let write some applications, waits there.
An important note should be taken; due to the business consideration, the cloud-provider considered a semi-honest adversary that is semi-honest adversary obeys the protocol however, they can use all information they observed and deduce more if they can. Over time we understood that this approach is not correct. We should consider them as a covert adversary,

Covert
adversaries have the property that they may deviate arbitrarily from the protocol specification in an attempt to cheat, but do not wish to be “caught” doing so

So if you plan to store your data, even only for storage, use authenticated encryption to produce the integrity and authentication of your data. A Merkle Tree-based approach is necessary to ensure the freshness of your data ( to detect a possible rollback).


What does $1^n$ mean? I often see the notation of powers of 1 in cryptography papers.
For example, let $n$ be security parameter, then what does $1^n$ mean??

From high school student perspective, powers of one is always one....
But I hope this is not.
Is this a bit string of length $n$?
If so why don’t they write it as $\{0,1\}^n$?

Is this a bit string of length $n$? If so why don’t they write it as $\{0,1\}^n$?

$\{0,1\}^n$ is not "a string of length $n$", it is the set of all strings of length $n$ (formally, the Cartesian product of $n$ copies of the set $\{0,1\}$). $1^n$ is an element of this set; namely the one where all bits are $1$.


Is there a practical upper limit for password rehashing? When using PBKDF2, is there a practical upper limit to the iteration count above which we lose security?

Note: If you answer “No”, that's fine. But if you answer: “There can't be an upper limit“, Consider the case of $2^{256}$ iterations using SHA-256.

When using PBKDF2, is there a practical upper limit to the iteration count above which we lose security?

No.

There is a limit above which you gain no security, but it isn't practical. It's on the order of $2^{128}$ iterations for PBKDF2-HMAC-SHA-2, or $2^{80}$ if you use SHA-1 as the HMAC hash. For an explanation, see the questions mikeazo linked in the comments.

However, due to the structure of PBKDF2 those collisions in the iterated hash likely don't undo the previous iterations, they only add to them (XOR). So the fact that you get collisions in the iterated function does put a limit on how much security you can gain from a high iteration count, since an attacker could stop iterating if they notice a collision. Nevertheless, they need to get that far and the ultimate hash is probably still different from all the other passwords, so that doesn't mean those extra iterations make it weaker.

Cycles, which you would notice about the same time, can technically "undo" previous iterations, but the unique iterations before the cycle begins are still strong, and the expected number of those is also close to $2^{128}$ for a 256-bit hash.


Bicliques for permutations So I'm trying to understand the complexity of the biclique attack on Grostl and I have some questions:

1) The paper introduces sliced bicliques where on Grostl one constructs a biclique of dimension 1 and accordingly, we get 4 $Q's$ at state#5 and 4 $P's$ at state#8. What I understood is that each pair of $Q's$ should hash to the same value at the matching point (state#13), similarly for the $P's$. My question is how is this possible if we have 4 different $Q's$? My understanding is that can happen if we consider only the parts at state#13 that are not affected by the difference (white bytes), is my undarstanding correct?

2) The complexity of the attack should be equal to #bicliques(cost of biclique construction + cost of computing forward and backwards to the matching point + cost of checking for a full match if partial matching took place), right?

3) Cost of biclique construction is the $2^{70}$ for the super Sbox solutions and consequently using the free 48 bytes in the $Q's$, we can have $2^{384}$ bicliques without the need to construct new one. However I cannot understand the $2\times(8 + 16 + 2 + 7 + 56 + 8) = 194$ Sboxes for both the forward and backward recomputation. I understand that we're supposed to recompute the white bytes that affects the 4 leftmost columns white bytes at the matching states only but howcome there are 6 terms in the above computation althought we only have 2 rounds in each direction after the biclique? and how are the 194 Sboxes equal to $2^{-3}$ call of the permutation if the 10-rounds permutation has 640 Sbox lookups in Total?

4) What about the complexity of checking for the full match if we get a partial match?

Thanks in advance.

A sliced biclique over $g$ is two set of states ${Q_{i,j}}$ and ${P_{i,j}}$ such that for every pair $(i,j)$
$$
P_{i,j} = Q_{i,j}.
$$
The states are chosen so that the difference between $Q_{i,j}$ for fixed $i$ is small, and the same must hold for $P_{i,j}$ and fixed $j$.

$Q$ and $P$ map to the same hash value $H$, but it is not state #13, but rather
$$
H = \#1\oplus\#13.
$$
You use this equation to filter out incompatible pairs $(i,j)$. The entire trick is to treat some $Q$ as the same, and similarly with $P$ to reduce the computations.

So to answer your other questions

2) Right

3) These are the numbers of recomputed S-boxes in each round from 1 to 6th. There are $6*64 = 384$ S-boxes in total, so there must be $2^{-2}$ calls, not $2^{-3}$.


Extract one unique SBox from Canonical Representative In paper https://eprint.iacr.org/2011/218.pdf, the author has examined 16! different 4 bit SBoxes and at the end of investigation, introduced an  optimal class which named "Golden SBoxes". How can I extract one SBoxes from this class?

I mean by knowing the canonical representation of Golden SBoxes as "035869C7DAE41FB2","03586CB79EADF214","03586AF4ED9217CB" and "03586CB7A49EF12D"(table 4 of paper),

how can I extract the golden sboxes such as Serpent S-Box S3, Hummingbird-1  SBoxes S1, S2, and S3 and Hummingbird-2 SBoxes S0 and S1?

This illustrates the idea with no efficiencies considered. Take the canonical Sbox, and let $$X:=[X[1],\ldots,X[16]]$$
be the vectors in $\{0,1\}^4$ in the order given by the canonical Sbox map.

Looping through all invertible $4\times4$ matrices $M_0,M_i$ and all constant vectors $c_0,c_i$ compute the list of column matrices
$$
F(M_0,M_i,c_0,c_i):=M_0 \cdot [M_i\cdot(X[1]\oplus c_i),M_i\cdot(X[2]\oplus c_i), \ldots M_i\cdot(X[16]\oplus c_i)]\oplus [c_0,\ldots,c_0],
$$
and you will find the target Sboxes for some $F$ computed during this process.

See extract from the paper quoted in the question below:


GPG symmetric encryption and javascript I have a use case where I need to encrypt some text in the browser using javascript. Only the encrypted text will be stored on the server. The user should then be able to take the encrypted result and decrypt it with GPG on the command line. I want to use GPG as it's easily available and the AES appears to support iteration on passphrase hashing.

I'm hoping to use AES, however I don't understand what iteration count or salt GPG uses.

For example, http://cheeso.members.winisp.net/AES-Encryption.htm allows you to set parameters for AES decryption using Javascript:

Does anyone know what parameters to use to be compatible with GPG ?

GnuPG follows the OpenPGP format, which is a protocol in its own right -- it uses AES (among other algorithms) but is more complex than "just AES with the right parameters".

There is at least one OpenPGP implementation in Javascript (I have not tried it, though).


Calculating $\mathbb F_{p^2}$-rational points of an elliptic curve defined over $\mathbb F_p$ How can I calculate points on an elliptic curve defined over $\mathbb F_p$, for example $y^2 \equiv x^3 + 1 \pmod p$, with coordinates in $\mathbb F_{p^2}$? (points might have complex number format in $\mathbb F_{p^2}$)

The general case is that of field extension. Given a field $\mathbb{F}_q$ of $q$ elements (in your case, the field is $\mathbb{Z}_p$, the integers modulo a prime $p$), you want to define and do computations in a field $\mathbb{F}_{q^k}$ of $q^k$ elements for some integer $k > 1$. To do so, one first considers $\mathbb{F}_q[X]$ which is the ring of polynomials with coefficients in $\mathbb{F}_q$: a polynomial is the formal sum:
$$ A = \sum_{i=0}^{\infty} a_i X^i $$
for some values $a_i$ (the "coefficients") in the field $\mathbb{F_q}$, such that only a finite number of $a_i$ are distinct from $0$. The degree of the polynomial is the integer $n$ such that $a_n \neq 0$ but $a_i = 0$ for all $i > n$.

Polynomials can be added together, and multiplied together, in the natural way. If we define:
\begin{eqnarray}
A &=& \sum_{i=0}^{\infty} a_i X^i \\
B &=& \sum_{i=0}^{\infty} b_i X^i \\
\end{eqnarray}
then the sum of $A$ and $B$ is:
$$ A + B = \sum_{i=0}^{\infty} (a_i+b_i) X^i $$
and the product is:
$$ AB = \sum_{i=0}^{\infty} \left(\sum_{j=0}^{i} a_j b_{i-j}\right) X^i $$

There is a well-defined Euclidian division of polynomials: given polynomials $A$ and $B$, with $B$ being non-zero (the "zero polynomial" is the polynomial whose coefficients are all equal to zero), then there exist unique polynomial $Q$ and $R$ such that $A = BQ + R$, and the degree of $R$ is strictly less than the degree of $B$. (For this definition to work, we formally define the zero polynomial to have degree $-1$.)

If we can compute additions and multiplications, and we have an Euclidian division, then we can define a modulo operation: "$A$ modulo $B$" is the value $R$ in the equation $A = BQ + R$.

Now let's choose an polynomial $M$ of degree $k$ in $\mathbb{F}_q[X]$. To make things simpler, we choose a unitary polynomial, i.e. such that its highest non-zero coefficient $m_k = 1$. We then define $\mathbb{F}_{q^k}$ to be the quotient of $\mathbb{F}_q[X]$ by $M$: this is the set of polynomials of degree strictly less than $k$, and all operations (additions and multiplications) are taken modulo $M$. In other words, when adding and multiplying polynomials, we do as described above, with the additional rule that $M$ is zero, i.e.
$$ X^k = \sum_{i=0}^{k-1} -m_i X^i $$

This defines a ring. The beauty of the construction is that IF the polynomial $M$ is irreducible in $\mathbb{F}_q[X]$ (meaning that there exists no polynomials $U$ and $V$ of degree strictly greater than $1$ and strictly lower than $k$ such that $M = UV$), then that ring is a field. Another additional (and unobvious) property is that the choice of $M$ does not actually matters much, in that all fields $\mathbb{F}_{q^k}$ are isomorphic to each other, i.e. they describe the same inner structure. This is why we may talk of "the" field $\mathbb{F}_{q^k}$.

The field $\mathbb{F}_{q^k}$ is called the field extension of $\mathbb{F}_q$ of degree $k$. We formally map elements of $\mathbb{F}_q$ to the polynomials of degree $0$ in $\mathbb{F}_{q^k}$, which allows us to say that $\mathbb{F}_q$ is a subset of $\mathbb{F}_{q^k}$.

In your specific case, let's see what the above becomes. Your base field $\mathbb{F}_q$ is $\mathbb{Z}_p$, the integers modulo a prime integer $p$. You want a field extension of degree $2$, so you need an irreducible polynomial $M$ of degree $2$. To make computations easier, you would prefer $M$ to be as "simple" as possible, i.e.:
$$ M = X^2 + \alpha $$
with $\alpha$ chosen such that multiplications by $\alpha$ are easy. You also need $M$ to be irreducible (since you want a field), which here means that $-\alpha$ must NOT admit any square root in $\mathbb{Z}_p$. A very common choice here is to choose $p$ such that $p = 3 \pmod 4$, because then we can set $\alpha = 1$. If you do that, then $M = X^2 + 1$. In application of the rules above, this defines $\mathbb{F}_{p^2}$ to consist in polynomials $A = a_1X + a_0$ for all values $a_0$ and $a_1$ in $\mathbb{Z}_p$, and the additions and multiplications are done "naturally" with the extra rule that $X^2 = -1$.

If instead of writing $X$ you call it $i$, then you get the same construction as complex numbers $\mathbb{C}$ from real numbers $\mathbb{R}$, and the easy computation rules that @Cryptostatis lists in his answer. There is, notably, a possible extra optimization when implementing:
\begin{eqnarray}
(a_0+ia_1)(b_0+ib_1) &=& (a_0b_0 - a_1b_1) + i(a_0b_1 + a_1b0) \\
&=& (a_0b_0 - a_1b_1) + i((a_0+a_1)(b_0+b_1) - a_0b_0 - a_1b_1)
\end{eqnarray}
That is, the product of two values in $\mathbb{Z}_{p^2}$, with the modulus $M = X^2+1$, can be computed with only three multiplications in $\mathbb{Z}_p$.

For further information on finite fields, and details on the construction of field extensions, the very classic read is A Course in Number Theory and Cryptography by Neal Koblitz.

(From your question, I suppose that you want to dabble in Weil and Tate pairings; thus, you need to be able to navigate through somewhat hairy mathematics, and Koblitz' book is almost a must-read for that. When you master field extensions, proceed with Ben Lynn's PhD thesis, which I found to be a nice read on that subject.)


When was the RSA 64-bit key introduced into internet encryption? When (if ever) was a key length of 64 bits used in "internet encryption" and when was that "cryptographic standard" first introduced?

Following up, when did "internet encryption" key lengths change to 128-bits, then to 256-bits, 512-bits and so on up to 2048-bits? Was the same "cryptographic standard" used?

The RSA paper from 1977 recommends the following on page 9:

  We  recommend  using  100-digit  (decimal)  prime numbers p and q, so
  that n has 200 digits.

200 digits is 663 bits, which would have been pretty strong in 1977. Due to the US government instituting export controls on cryptography in the early 1990s, 512 bit RSA became widely implemented as it was the maximum allowed for export.  I can't find any examples of keys smaller than 512 bits being used in practice, other than in the RSA factoring challenge.


Why do we use groups, rings and fields in cryptography? I'm a student of Masters in Cyber Security. I have a habit to understand things from their first principles (at the very beginning). Kindly use any simple mathematical example to answer because I have read plenty of technical answers but they aren't clear to me. For example, we use primes because we know factoring them is extremely hard. Furthermore, we use injectives because we don't want one to many relations in encryption because it will be a disaster on the decryption side. Same like my examples can you provide me an example of using groups that makes sense as primes and injective do?Kindly, let me know what was the actual problem which leads us to use groups in cryptography?
I know what a group is and its properties, I know about abstract algebra, but I don't know why we use them and what happens if we don't use them.

Kindly, let me know what was the actual problem which leads us to use groups in cyptogrpahy?

Well, we use groups and other similar mathematical constructs because:

We found there are problems that appeared to be difficult to solve with those groups

We found ways to translate the difficulty of solving those problems into the cryptographical strength of some object (such as an RSA public key encryption, or a signature), that is, you can't break the cryptographical object (e.g. decrypt the encrypted ciphertext without the key) unless you can solve the hard problem.

The second part is crucial; we know problems that are much harder to solve than the ones we use in cryptography; however we don't know how to exploit those.
That's pretty much the answer; the answer to "why do we use groups" is pretty much the same as Willy Sutton supposedly gave to the question "why do you rob banks" - "because that's where the money is" - that is, we do it because it provides the cryptographical security we're looking for.

I believe if I don't know "why" then everything is useless.

Then you're in trouble with cryptography - one of the things we do not know is why these hard problems are actually hard (if, in fact, they are) - the most we know is that a number of fairly bright people have tried to do a number of rather clever tricks to solve them, and none of them worked.


How distinct are the meanings of the terms "CSPRNG," "DRBG" and "stream cipher"? Are there universal, consensus definitions for the following terms?

Cryptographically secure pseudo-random number generator ("CSPRNG")
Deterministic random bit generator ("DRBG")
Stream cipher

This is primarily a question about the terminology rather than the concepts (although I do not master the concepts by any means either).  My confusion arises because:

I recall seeing some reference (that I can't find again now) which equated CSPRNGs and stream ciphers, due to the fact that expanding a finite key to a long, secure keystream is basically the same problem as generating a long cryptographically-secure pseudo-random sequence from a short seed.  So correspondingly, stream ciphers are sometimes used as PRNGs, as in for example Rust's ChaChaRng.
The term "DRBG" appears to be mostly used by NIST in connection with their SP 800-90A algorithms, and which stresses safety against adversaries who can observe the state at one point in time.  The key concepts here, as I understand them, are forward secrecy and periodic reseeding from external entropy sources.
The term "CSPRNG" apparently gets used in both senses (see for example the answers to this question).

The definitions are not all universal and there is quite some overlap.

The clearest definition is for PRG, which is the (synchronous) stream cipher model. A PRG maps a secret value to a long, random-looking keystream, so that an attacker cannot predict any part of the keystream from knowing other parts of it. For a precise definition, you can see the definition in Katz and Lindell (3.15 in my copy) or find the equivalent in some other textbooks.

Of course, there is the catch that most modern stream ciphers do not really fit just the PRG model (even if they are synchronous). They use an IV/nonce, allowing for multiple uses of the same key.
NIST defines DRBG as:

generating a sequence of bits that appear statistically random and independent
in a deterministic manner
from a seed (and possibly other inputs).

This sounds very much like a PRG, except for the other inputs, but they also mention access to an entropy source. It is quite vague and they also say that:

  A DRBG is often called a Pseudorandom Number (or Bit) Generator.

Clearly there is overlap.
CSPRNG is basically a catch-all term for random number generation that is cryptographically secure in some sense. I don't know that you will find a consensus on what it should mean. (Personally I would require things like reseeding and forward-secrecy, while perhaps also defining a way to map the bit sequence into random numbers, but those are not universally assumed.)

There are also ways of turning one of these into another, like the stream cipher -> RNG you mention, because these are after all requiring similar properties, if not exactly the same.


Substitution ciphers amended with cipher block chaining: susceptible to frequency analysis? I have been studying ways to amend a simple substitution cipher, and one of the toy suggestions was to use CBC in the following way:

identify each letter with a number from $0\ldots 25$
start with a random IV, i.e. just a random letter
add IV to the first letter in the plaintext, modulo 26, and then encrypt according to the old substitution rules

(then continue with CBC in this way, using modulo 26 arithmetic instead of XOR)
The resource then goes on to say that while this clearly can't be cracked by simple frequency analysis on letters, the ciphertext can be split into 26 sets, that is, the letters that follow each ciphertext letter, and then frequency counting can be done. Later on, the author reiterates that by partitioning the message into 26 groups that follow each ciphertext letter, frequency analysis can be done.
I've been trying to figure out what they meant by this. My main problem is trying to interpret the "26 groups that follow each ciphertext letter" part, and I didn't get anywhere with it. (Perhaps they meant grouping sets of 26 adjacent ciphertext letters together, and then modular arithmetic would ensure some repetition somehow? I don't really see how that would work, but I also don't see any other interpretations)
Would greatly appreciate any suggestions!

CBC in this context means that each letter of the ciphertext is used to help encrypt the next letter.
Let's say, making up some numbers, that a certain ciphertext letter is C. The next plaintext letter is T. So to encrypt it, we will add C (or 2) to T, giving V. Then we do the substitution step, which could be anything and happens to be J.
The key observation here is that every time there is a C in the ciphertext, the next letter goes through the same thing. Plus two, substitute. And every time you find a C in the ciphertext, the next letter all Ts go to Js.
The break, then, is to go through the ciphertext looking for Cs. Then you write down all the letters that immediately follow. You get 200 Rs, 160 Js, whatever it is. So you can conclude that after a C, E is probably mapping to R and T is probably mapping to J.
Do the same thing with other letters: everything following Ds, everything following Es, and so on. You'll have 26 different sets of letters to do frequency analysis on. And once you have done them, you'll know the substitution several times over.


rsa public and private keys I have a question about RSA key generation.

This is a simple RSA algorithm:

Choose p = 3 and q = 11
Compute n = p * q = 3 * 11 = 33
Compute ?(n) = (p - 1) * (q - 1) = 2 * 10 = 20
Choose e such that 1 < e < ?(n) and e and n are co-prime. Let e = 7
Compute a value for d such that (d * e) % ?(n) = 1. d=3
Public key is (e, n) => (7, 33)
Private key is (d, n) => (3, 33)

So public and private keys are numbers. but in many online encryption websites keys are like this:

d94d889e88853dd89769a18015a0a2e6bf82bf356fe14f251fb4f5e2df0d9f9a94a68a30c428b
39e3362fb3779a497eceaea37100f264d7fb9fb1a97fbf621133de55fdcb9b1ad0d7a31b379216
d79252f5c527b9bc63d83d4ecf4d1d45cbf843e8474babc655e9bb6799cba77a47eafa83829647
4afc24beb9c825b73ebf549

How are those keys actually generated?

The key you wrote down contains a mixed alphabetic and digit symbols because it is written in its hexadecimal representation: i.e. using symbols from 0 to 9 and from A to F. More on this topic on Wikipedia page.
You can easily convert hexadecimal to decimal using software as python, sage, Pari/GP and many others.
An online converter could be found here: Hexadecimal to Decimal Converter

About the key generation, the process is the same you described but with bigger numbers: a standard RSA key uses primes of about 1024 bits. The real different part is find a prime number of such size: there are some algorithms that outputs a number of wished size and (with high probability) prime.


Do 'nonsequential' PRNGs exist? It is my understanding that PRNGs typically use a seed and can then generate random values one after the other. This is what I mean by being 'sequential'.

How about a PRNG which allows me to retrieve e.g. the third value, without computing the first and second? Basically, I'm looking for a function $g: \mathbb{N} \rightarrow (\mathbb{N} \rightarrow \mathbb{R})$ such that for all seeds $n \in \mathbb{N}$, $g(n)$ is a function who's values follow some specified distribution while computing $g(n)(m)$ takes constant time.

How about a PRNG which allows me to retrieve e.g. the third value, without computing the first and second?

That is a popular informal description of what a pseudo-random function is—a function constructed out of a random seed that, for any input, produces a pseudorandom output in a repeatable fashion (i.e., same input always gives you the same pseudorandom output).

The suggestion in the comments to use CTR mode is along these lines—CTR mode is the application of a PRF to a sequence of counter values.  I.e, if $f : K \to I \to O$ is a pseudorandom function family, $k \in K$ is a randomly selected secret key, and $i_0, \dots, i_n \in I^*$ is a sequence of distinct values in the domain of $f_k$, then the sequence $f_k(i_0), \dots, f_k(i_n)$ cannot be efficiently distinguished from a sequence of values drawn at random from $O$.

Some practical choices of PRF would be:

HMAC
Any block cipher (e.g., AES). These are pseudorandom permutations—bijective PRFs—which means that they cannot be distinguished from a general PRF unless the number of queries exceeds the so-called "birthday bound" (search for "PRF-PRP switching lemma").


Is MD5 particularly vulnerable when given multiple MD5 hashes using a common, secret suffix? Suppose I've got a list of "passwords" that are hashed using the same suffix, so basically what we do is hash = md5_digest(prefix+suffix), with suffix being a constant.

Now, if I know a single prefix and hash pair, I can trivially do a brute-force search for suffix.

But given multiple different known matching pairs of prefix and hash, is there a better than brute-force way of finding the value of suffix? Is there an algorithmic vulnerability of MD5, relying on the internal state that would allow me to do this? Or, alternatively, to construct a fake prefix that would generate a known hash when concatenated with the unknown suffix?

Update: Please don't suggest alternative hashing schemes, as I'm not designing a system or anything, I just want to understand how MD5 works.

Update 2: Okay, I might not have made myself clear enough. I'm not interested in any other "solution" for the simple reason that my problem isn't "how do I secure this system?" but "how does this specific algorithm behave?". Yes, I do know the difference between a hash algorithm and message authentication, yes, I do know HMAC, yes I do know MD5 is broken.

is there a better than brute-force way of finding the value of suffix?  Is there an algorithmic vulnerability of MD5, relying on the internal state that would allow me to do this?

The best attack better than brute-force I could found is described in this paper, it has a complexity of 2^123.4 and a memory complexity of 2^45×11 words. AFAIK this is not practical

  Or, equivalently, to construct a fake prefix that would generate a known hash when concatenated with the unknown suffix?

This is not equivalent to your first question. Your first question is a preimage attack, meaning finding the original value (prefix + suffix) that generated the hash.

This question can be interpreted in two ways:

You're asking for an algorithm that can generate a second pre-image, meaning a second value different from the original one that produces the same hash. In this case there is no known second pre-image attack against MD5
You're asking if it's possible to find a collision for a given hash using a fixed part in the message. To this question I only know there are algorithms to efficiently find collisions for a given MD5 but I don't know if those methods can be adapted to use a fixed part in the message (The suffix)


Can you really insert the text you want in one-time pad? The Wikipedia article "One-time pad ~ Authentication" says :

  For example, an attacker who knows that the message contains "meet jane and me tomorrow at three thirty pm" at a particular point can replace that content by any other content of exactly the same length, such as "three thirty meeting is cancelled, stay home", without having access to the one-time pad, a property of all stream ciphers known as malleability.

I don't quite understand how it's possible.

Let's say the string is encrypted using one-pad time. Hacker somehow gets that encrypted text and he knows that the last word contains 6 chars. So, he removes last 6 chars from the ciphertext and he wants to add his own 6 character word. How he can do that?

If he just inserts that word, after the decryption that inserted word becomes most likely just gibberish. Or am I wrong?

It is quite simple and stems from the idea that flipping one bit in the ciphertext flips the corresponding bit in the plaintext.

So, say the ciphertext is $1011$ and we know the plaintext is $0101$ (thus the key is $1110$). Say we want a plaintext of $0000$, we just have to change the ciphertext to $1110$ (notice where the bits have been flipped) and we have $1110\oplus 1110=0000$

In that sense you if you can flip any bits you want and you know what the plaintext says and you know what you want the plaintext to say, you flip the right bits in the ciphertext and decryption comes out as you desired.


Signing a message to make sure that it will not be tampered with when forwarded, without trusting the receivers? Lets say there are 3 people.

1st signs a message and sends it to 2nd using public key encryption
1st deletes the message
1st tells 2nd to forward his message
2nd forwards the message to 3rd

How can 1st verify the message was forwarded untampered without trusting 2nd or 3rd and without finding out the message contents again?

A terrible idea is to have 3rd give his private key to a 4th who will confirm to 1st that his message was untampered.

I am new to this so if what I want to do is impossible a heads up would be deeply appreciated.

I see this as a mixture of easy and impossible.  A standard digital signature will work to verify the contents, as long as the document+signature is sent to person 1 (or whoever wants to check the document)

The impossible part comes if you only want person 1 to only have the signature and not the document.  Even if person 1 keeps a copy of every signature, Person 2 can send a tampered document with the original signature.  Person 3 would know the document has been tampered, but if 3 wants to be part of the deception they can just send the original signature to person 1.


S-AES RC[i] Generation. Can someone explain how to generate the RC[i]s for these two problems I have? I don't know exactly how to find the RC[ 1 ] of 80, or the RC[2] of 30.
Can someone explain how to find them?

Here is a picture of the problem I am having with two questions.

Your question missing some information about the source, however, one can give an answer based on S-AES i.e. Simplified AES.

There is a nice definition of S-AES here.

The Round Constant (RC) or the other name R-con has 10 values for AES and utilized for the key schedule to eliminate the symmetry by making each step of the key schedule slightly different.

i      1   2   3   4   5   6   7   8   9  10
RC[i] 01  02  04  08  10  20  40  80  1B  36

S-AES has defined only 2-rounds, thus the designers of S-AES have to choose only; two RC values. This is just a selection issue, not a generation as in AES-key schedule.

RCon[1] = 80
RCon[2] = 30

Note: S-AES is only an oversimplified AES for educational use.


Are there any deterministic multi-block encryption constructions that have an avalanche effect going both ways? For common multi-block encryption schemes (CBC, CTR, CFB, stream ciphers, etc), if they are forced to be deterministic, a change in the plaintext will change only the current block and maybe future blocks, but the past blocks are unchanged.

Using DES-CBC as an example, I've fixed the IV as to force it to be deterministic. (DES is used here for the small block size, for convenience)

Input:  0001020304050607 08090a0b0c0d0e0f 1011121314151617 18191a1b1c1d1e1f 2021222324252627 28292a2b2c2d2e2f
Output: 4c72f896d0b5c010 96cafa256bd7bf8c 7f3dfa17eb0721d6 2db73b14cfa32977 e87a8caf18ace662 298640486525ca14

Now to change one bit in the third block.

Input:  0001020304050607 08090a0b0c0d0e0f 1011321314151617 18191a1b1c1d1e1f 2021222324252627 28292a2b2c2d2e2f
                                              ^ Change
Output: 4c72f896d0b5c010 96cafa256bd7bf8c 123ea45b2bc1d45b 876ee075d04e5c61 ea59edd03137781b 57cd1fafa7849fe2
                                   Change ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^

You'll notice that the first two ciphertext blocks are the same.

Are there any deterministic constructions that allow for any change of any bit in the plaintext to affect every bit of the ciphertext?

I know no classical deterministic multi-blocks encryption construction with the desired avalanche property. And a serious problem is that any such construction, simply because it is deterministic, won't pass the formal definition of security under chosen plaintext, which CBC, CTR, CFB, OFB.. with random IV achieve.

So what's asked does not come with a precise definition of security. Given this, I can state anything without risk of contradiction from the standpoint of security. So here is something, essentially two passes of CBC encryption with IV the last block of the previous pass. For encryption:

Pad de message to an integer number of blocks; e.g.: append a single bit 1, then as few bit(s) 0 (possibly none) as strictly necessary to reach a multiple of the block size.
Let $b>0$ be the number of blocks of padded plaintext $X$
If $b=1$, do $X_0\gets E(E(X_0))$ where $E$ is block encryption
Otherwise repeat for $i$ from $b$ to $3b-1$ (that is, $2b$ times):

$X_{i\bmod b}\gets E(X_{i-1\bmod b}\oplus X_{i\bmod b})$

Output ciphertext $X$

Decryption is:

Let $X$ be the ciphertext of exactly $b>0$ blocks
If $b=1$, do $X_0\gets D(D(X_0))$ where $D$ is block decryption
Otherwise repeat for $i$ from $3b-1$ downto $b$ (that is, $2b$ times):

$X_{i\bmod b}\gets X_{i-1\bmod b}\oplus D(X_{i\bmod b})$

Remove padding; e.g.: while $X$ ends with a zero bit and is non-empty, remove the rightmost 0 bit; then if $X$ is non-empty, remove its last bit.
Output the plaintext $X$

We can improve diffusion in decryption by using PCBC rather than CBC, make the thing less malleable by throwing an extra $\oplus i$, do more passes, have an extra index hopping into $X$, derive a different key at each pass.. but without a definition of the security goal, that is moot.

Note: as pointed out elsewhere, plaintext changes do not propagate at all in CTR mode, contrary to the question's statement.


Building a hard to factor number without knowing its factorization It is possible to find an efficient algorithm for constructing a provably hard to factor number $N$, together with a witness that shows that it is indeed hard to factor. EDIT, since it was not clear: I also want to be sure that even the person that constructed the number cannot factor it.

Of course, a random large enough integer is going to be hard to factor with high probability, but we might be unlucky.

There are also multi-party protocols for shared generation of RSA moduli (such as http://crypto.stanford.edu/~dabo/abstracts/sharing.html), but I would like a non interactive technique.

Motivation: This was suggested by Poncho's answer to Compare two hashes with different salt

The zerocoin paper mentions such a technique:

  implementers can use the
  technique of Sander for generating so-called RSA UFOs
  for accumulator parameters without a trapdoor

and refers to:

  T. Sander, “Efficient accumulators without trapdoor extended
  abstract,” in Information and Communication Security, vol.
  1726 of LNCS, 1999, pp. 252–262.

I can't access it since it's behind a paywall, but according to a comment by Hal Finney they're rather large:

  As far as the Sander paper, trust can be minimized by seeding a random number generator from a public headline. The real problem with this approach is that it generates ridiculously large RSA moduli. One example they give in their paper is 40,000 bits!


What procedure to use to verify a raw public key (TLS ECDHE_EDCSA ciphersuite)? Contrary of verifying a certificate which is a well-known procedure, I am wondering what the procedure is to verify a raw public key 'certificate' (https://tools.ietf.org/html/rfc7250). This certificate, as a matter of fact, does not carry any signature.

It is outside the scope of TLS and must be arranged out of band.

Raw public keys come without any signatures and cannot be verified without additional knowledge. Section 1 of the RFC mentions a few ways how they might be verified in some situations. They all amount to receiving the public key through some other authenticated channel.

  The TLS client can obtain the TLS server public key from a DNSSEC-
    secured resource record using DNS-Based Authentication of Named
    Entities (DANE) [RFC6698].
  The TLS client or server public key is obtained from a [PKIX]
    certificate chain from a Lightweight Directory Access Protocol
    [LDAP] server or web page.
  The TLS client and server public key is provisioned into the
    operating system firmware image and updated via software updates.


Is it possible to do a known-plaintext attack with this set up of AES CTR mode? Is it possible to perform a known-plaintext attack to extract the key from AES byte encryption?

The encryption is setup with the following two lines:

ctr = Counter.new(128)
crypt = AES.new(key, AES.MODE_CTR, counter=ctr)

And we have both the plaintext and the ciphertext

The answer is simply no;

The known-plaintext attack on AES-CTR mode will reveal the encrypted output of the AES
$$c_i = p_i \oplus E_k(ctr+i)$$
$$ c_i \oplus p_i = E_k(ctr+i)$$

and since in the counter mode, we know the counter values (input to the AES in CTR mode), we can see this as known-plaintext attack on ECB mode.

The possibility of known-plaintext attack on AES in ECB mode is given lately as;

  No. This is what is referred to as a known plaintext attack, and secure block ciphers are designed to prevent exactly this kind of attack. This answer on the Mathematics Stack Exchange goes into more detail about the notion of IND-CPA ("indistinguishability") which AES is conjectured to meet and how that implies that a known plaintext attack is impossible.


Why was the Navajo code not broken by the Japanese in WWII? In reading about this topic recently, to my understanding, the encryption schemes used on top of the Navajo language were very simple and definitely could have been broken (my research shows they mapped Navajo words to various different meanings).

The Navajo language alone is obscure, had few speakers, and was not a written language - but still I'm amazed that the code was never broken. Isn't this an example of "Security through obscurity"?

No matter how obscure the language was, the sounds still mapped to English phrases at the end of the day. Through cryptanalysis, shouldn't the Japanese have broken the code? Am I missing something here, or is this an example of security through obscurity actually working?

Edit:
Follow up question: Could a similar scheme work today?

Wrapping up my comment as an answer:

Imagine you’re a Japanese cryptanalyst in the year 1944. There is no such thing yet called “television”, and you’re still decades away from a wordwide network feeding you with all the knowledge you could wish for.

In that case there’s only a minimal chance you’ve ever heard or seen a Navajo. So, you’ll be wondering what “Joe” is talking about as it sure doesn’t sound like English. You‘ll be asking yourself things like: Is that the plaintext in some language I don’t recognize or simply a failed decryption attempt?

Furthermore, even if you would know it is Navajo and assuming you would have some plaintexts to your availability, you would still be wondering about the more simple things of cryptanalysis, like: What’s the character frequency of Navajo anyway?

Even more, since Navajo is a descriptive language. Even having things like character frequencies and plaintexts at hand,  how would you know what is meant by (eg) “wolf feeds bisons when eagle moon embraces cloud rock”?

See, Navajo indians may know “cloud rock” from stories told by their elders and they may know the exact day in the year when the “eagle moon embraces“ it… but you – sitting in your cryptanalysis room in Japan – have a rather minimal chance of even grasping half of it.

All in all, the use of Navajo boils down to a suplemental layer of “security through obscurity”. Maybe it helps if you think of the Navajo communicators as “living codebooks”. Embedding them (especially in key positions) added an additional layer of security to the already used cryptographic protection during radio communication et al.

In fact, take the actively used (radio) encryption during WW2 and add a layer of Navajo language use on top of it, and you’ll end up with something that could almost be called “double encryption”.

edit

To answer the additional question from your comment (now follow-up question added as an edit)…

  I think both of these are good explanations of why this scheme worked. From your explanations it seems to me the primary reason it wasn't broken is because it happened 70 years ago. Am I correct in saying this would never work today?

Under most conditions – Yes, that’s correct.

Of course, this depends on the exact situation. The reason I’m saying that is that there aren’t many Navajos living today (last I heard was something in the thousands). Some specific scenarios might change that “yes” to a “no”. But generally, looking at the means (and resources) available today, I tend to say that – in contrast to the WW2 – they indeed wouldn’t be very helpfull in terms of security. Actually, it’s like using the Klingon language from Star Trek, or Elvish from Lord of the Rings… as long as only a few know it, it might add a minimal bit of security. But nowadays, you can even take online courses to learn Klingon, Elvish, etc. Back in 194-something, the situation was quite different.

As an aside: I used the name “Joe” on purpose, since it was a commonly used nickname for US-American soldiers during World War 2. Another example of such a naming would be “Tommy“, which was used to hint at English soldiers.


Evaluate hash function I am trying to figure out how to evaluate the security of a hash function. If I have defined a candidate hash function: $$H(x) = α^x\text{ mod }p$$ how do I then evaluate it with respect to collision attacks, second preimage attacks, and preimage attacks? Hope someone can help

If $x=y \mod \phi(p)$, then $H(x)= H(y)$. Then it doesn't seem collision resistant.
For the same reason not second preimage attacks. $H(x + \phi(p))= H(y)$.
(If $p$ is prime $\phi(p)=p-1$, thus it's easy to compute it).
About the preimage attack, it's completely equivalent to discrete logarithm in $\mathbb{Z}^{\star}_p$, then you have to be carrefull about the choice of $p$ (basically $p-1$ should have a huge factor).


2 comparable hashes generated from one string Assume a website where people log in with their password.

The password is now stored in sql database as:

md5(password + random_salt)

We are adding the possibility for clients to stay logged in and I am trying to find out the best way to do that.

Passwords should stay stored in the DB as hashes using some hash function (with the use of a generated salt) - first hash
When client logs in with his password, a different hash of his password should be generated (using the previously generated salt) and stored in the relation "second hash".
These two hashes should be comparable to each other, so that I could check if the second hash (generated during login) originates from the same string as the first one (generated during registration).

The second hash (the "login" one) would also be used to generate a key to encrypted sensitive user files (probably using AES, or is there a better option?).

I am quite new to this and I'm not sure if I am not being too naive, so I am asking. Is there a way to achieve this? Is there any source where I could read about these "comparable hashes"? I tried searching but I don't really know what to look for.

Deriving an encryption key and a password hash from a single password
Hash the password, along with a per-account salt.
hash1 = SHA256(password, salt)

hash1 is your encryption passphrase that you pass to GPG.
hash2 = SHA256(hash1)

You keep hash2 in your database to figure out when a user has logged in correctly.
(For additional security, change the first SHA256 out for scrypt, tuned for 50 milliseconds. More trouble than it's worth, IMO.)
Encrypting a file
Use a library like GnuPG. If you don't have GnuPG bindings for your language (I'm guessing you're using PHP), you can hack something together by running gpg from your program with the  -c and --passphrase arguments.
Note that if the user changes their password, you need to decrypt and re-encrypt using the new password.


Understanding the length extension attack I have been trying to understand exactly how a length extension attack works on SHA-1. I'll detail below what I've understood so far, so that I can convey my understanding of the same and hopefully get advice on where I'm going wrong.

Lets assume that for a message $m$, a secret $s$ is appended to it and the SHA-1 hash is calculated. If $\textrm{len}(m) + \textrm{len}(s)$ is not a multiple of the block size, a certain amount of padding is added to it to make it a multiple, and the hash is generated using what is essentially $s || m || \textrm{padding}$.

Now SHA-1 internally uses 5 registers — it takes in an block, generates new register values, turns the crank, takes in another block, generates new register values, turns the crank ... and so on till the end. When all blocks are exhausted, the register values are concatenated and spit out.

Assume that an attacker knows a certain value of $m$, for which he also knows the hashed key. In such a case, he knows the state of the 5 registers when $(s || m || \textrm{padding}$ was processed. Lets also assume that the attacker knows the length of $s$, so that he can predict how much padding was added.

Here is where I get confused. From what I've read so far, the attack involves taking the known hash, adding a certain amount of padding and then the value that we want. However, isn't the padding already used up in creating the hash? Why are we using padding in our attack?

SHA-1 processes data by 512-bit blocks (64 bytes). For a given input message m, it first appends some bits (at least 65, at most 576) so that the total length is a multiple of 512. Let's call p the added bits (that's the padding). The padding bits depend only on the length of m (these bits include an encoding of that length, but they do not depend on the value of the bits).

The padded message m||p is then split into successive 512-bit blocks, which are processed one after the other. SHA-1 uses an internal compression function (that's the traditional term); it also has a running state consisting of five 32-bit words. The compression function takes as input two values of 160 and 512 bits, respectively, and outputs 160 bits. The processing goes like this:

The running state is initialized to a fixed, conventional value (which is given in the SHA-1 specification).
For each input block, the compression function is evaluated, with as input the current running state, and the input block; the output of the function is the new running state.
The running state after processing the last block is the hash output.

So now, the length-extension attack. Suppose that you give me a hash value h, computed over a message m that is unknown to me. I know the length of m, but not its contents. Since I know the length of m, I can easily compute the padding p that you used. Then I imagine a message m', which begins with m||p; that is, m' = m||p||z where z is a sequence of bits that I can choose arbitrarily. I will now proceed to computing the SHA-1 hash of m', even though I do not know part of it (it begins with m, which I do not know).

When SHA-1 is computed over m', the latter is first padded with p', which depends on the length of m' (which I know). The resulting stream is m||p||z||p'. Then, the 512-bit blocks are processed one by one. I cannot do it for the first blocks, since I do not know m. However, I can imagine myself doing it. At some point, I would reach precisely the end of the p string (since the length of m||p is a multiple of 512). What would be the value of the running state at that point ? Well, that's exactly the hash value h that you gave me ! Therefore, I can stop imagining; I can start my SHA-1 computation of SHA-1(m') right at that point, at the beginning of z, using your hash value h as value for the running state.

That's the core of it. I can use SHA-1(m) to compute SHA-1(m'), a message which begins with the contents of m, and I can do that without knowing m. This property of SHA-1 (which applies to other Merkle-Damgård hash functions such as MD5 or SHA-256) is not in contradiction with the usual hash function security features (resistance to collisions, preimages and second preimages), but it shows that SHA-1 is not a random oracle.

What good can it do to the attacker ? Well, consider the following (flawed) construction for a Message Authentication Code: for a given key k and data to protect d, compute SHA-1(k||d) as the MAC value. This scheme breaks in the presence of the length-extension attack: if I, as an attacker, sees a MAC for a message d, then I can compute the MAC for a message d' which extends d -- and I can do that without knowing k||d (so, in particular, without knowing the key). This allows me to forge messages with a valid MAC.

The length-extension attack is the reason why, when building a MAC out of a hash function, we need something a bit more convoluted, namely HMAC (which is safe against it).


Usage of pairings in proxy re-encryption algorithm I am having trouble understanding one part of the AFGH algorithm for proxy re-encryption (my background in discrete mathematics is lacking a bit).

The paper describes the algorithm setup the following way:

"To minimize a user’s secret storage and thus become key optimal, we present the BBS [Blaze et al. 1998], Elgamal-based [Elgamal 1984] scheme operating over two groups $\mathbb{G_1}$, $\mathbb{G_2}$ of prime order $q$ with a bilinear map $e$ : $\mathbb{G_1} × \mathbb{G_1}$ → $\mathbb{G_2}$. The system parameters are random generators $g \in \mathbb{G_1}$ and $Z=e(g,g) ∈ \mathbb{G_2}$."

Both the key and re-encryption key generation parts are easy to understand, they're the same as in a regular ElGamal scheme. My question is in the first level encryption description, where the authors state that a $c$ must be computed such that $c = (Z^{ak}, mZ^k)$, where $k$ is a randomly selected element from $\mathbb{Z_q}$.

I don't understand exactly what $(Z^{ak}, mZ^k)$ are. Is $Z^{ak}$ the same as  $e(g^a, g^k) = e(g,g)^{ak}$ ?

And is $mZ^k$ the same as $e(g^k, g^k) = e(g,g)^{k^2}$ ?

EDIT: The paper can be found here.

EDIT: To clarify further:

While I can break down the maths behind an ElGamal scheme as

${c_1^{p-b-1}}{c_2} = ({g^k})^{p-b-1}m{(g^b)^k} = m[({g^{p-1})^k}{({g^k})^{-b}}]({g^k})^b  = m1^k(g^k)^{-b}(g^k)^b = m$

I can't do that for $(Z^{ak}, mZ^k)$ or $mZ^k$. I would like to understand the intermediate steps like I have for an ElGamal.

Is $Z^{ak}$ the same as $e(g^a,g^k)=e(g,g)^{ak}$?

That's correct: by the bilinearity property of the pairing $Z^{ak}=e(g,g)^{ak}=e(g^a,g^k)$.

  And is $mZ^k$ the same as $e(g^k,g^k)=e(g,g)^{k^2}$?

No it is not. $mZ^k$ is the group operation of $\mathbb{G}_2$ applied to $m$ and $Z^k$.

  I would like to understand the intermediate steps like I have for an ElGamal.

The first-level decryption algorithm, given a ciphertext $c_a=(\alpha,\beta)$, as per their specification involves computing $\beta/\alpha^{1/a}$. If the ciphertext is properly formed then $\alpha=Z^{ak}$ and $\beta=mZ^k$ and therefore
  $$\frac{\beta}{\alpha^{1/a}}=\frac{mZ^k}{(Z^{ak})^{1/a}}=\frac{mZ^k}{Z^k}=m.$$


Implementation of ECC over binary field I am supposed to implement ECC over binary field (in C++) for equations of the type - $y^2 + xy = x^3 + ax + b$, as my project. I wish to include the following features :

The user will enter a prime number $m$, which will serve as the order of the binary field as $2^m$.
For the given $m$, the irreducible polynomial will be generated.

  Q1. AFAIK, there is no method to efficiently find a random irreducible
  polynomial. The only way is to pick a random polynomial and check
  whether it is irreducible or not. (The polynomial can be no more than
  pentanomial, and trinomial in some cases) Am I thinking the right
  way?

The coefficients $a$  and $b$ will be generated.

  Q2. Can I use random number generator (with appropriate constraints)
  to generate $a$ and $b$ instead of producing it from a Seed $S$ ? Also, I have seen both Seed $S$ and the parameter $b$ being mentioned. What is the purpose to write both the things when $S$ is sufficient to generate $b$ ?

Various points that lie on the curve will be listed.

  Q3. To generate all the points, put $x=0, 1, 2 ...m-1$ and solve for
  $y$ for equations of the type : $y^2 + ky = l$. How to find the square
  root in such a scenario? Is there any better way to generate all the
  points?

Schoof's algorithm and the likes will be demonstrated to count all the points lying on the elliptic curve. (Though all the points have already been generated, but presenting an algorithm will be an added advantage)
A suitable base point $P$ will be chosen such that it has reasonably low cofactor.

  Q4. To find such a point, the order of each and every point should be
  found out. The only way that I can think of is : Pick a point $Q$.
  Find $2Q, 3Q$ until the points start repeating. Hence, one gets the
  order. Do so for all the points while maintaining the maximum order. Is there any better way to achieve
  it?

Finally an El-Gamal and/or Diffie Hellman analogous of ECC over binary field will be presented.

I would like to get clarification on above questions based on the mentioned scenarios. As of now, I don't have sufficient knowledge of ECC so it is pretty much possible that I have asked some nonsensical questions and I am really very sorry for it. Please feel free to share your ideas on these/any other features so as to make the project more worthy.

Q1.

Here's an algorithm to test irreducibility of a univariate non-constant monic polynomial over a finite field $\mathbb F_q$. (I learnt this from von zur Gathen and Gerhard's Modern Computer Algebra.)

Let $q=p^e$ be a prime power. A generalization of Fermat's little theorem states that for all $d\geq1$,
$$
x^{q^d}-x \;=\;\prod \{\,f\in\mathbb F_q[x]\text{ monic and irreducible with }\deg f\mid d\,\}
\text.
$$

Therefore, a monic polynomial $f\in\mathbb F_q[x]$ is irreducible if and only if $\gcd(x^{q^d}-x,f)=1$ for all $d\in\{1,\dots,n-1\}$.
This immediately yields an algorithm for testing irreducibility; it requires $\mathcal O(n^3\log(nq))$ elementary arithmetic operations when implemented correctly.

5.
If you are interested in a high-level description of Schoof's algorithm, have a look at this post of mine. (In particular, note that it is not exactly trivial to implement.)

Q4.

Suppose you have a prime factorization of the curve $E$'s group order (perhaps obtained using Schoof's algorithm followed by a factoring algorithm), say
$$n=\lvert E\rvert=\prod_{i=1}^k p_i^{e_i} \text.$$
Note that in any finite group, an element's order divides the group order. Hence you can easily check whether a point $P\in E$ is a generator by computing the powers $[n/p_i]P$: If
one of them is the identity, then $P$ is not a generator (since its order must then be a divisor of $n/p_i<n$), otherwise it is.
Now one can show (using the classification of finite abelian groups) that a randomly chosen group element is a generator with probability at least
$$
\prod_{i=1}^k\left(1-\frac1{p_i}\right)^{e_i}
\text,
$$
which should be "large enough" for practical purposes (when $n$ has few small prime divisors), hence you can find a generator by randomly picking points on the curve until you get one.


Does it make sense to use slow hashes in digital signatures? For storing passwords, it seems that the use of intentionally slow hash functions (like PBKDF2 and bcrypt) is now recommended. This is because most hashes are designed to be fast, which also makes certain attacks on them parallelizable on GPUs.

Now I'm wondering if it would make sense to use slow hash functions for digital signatures. Are collision attacks slower when the hash function is slower? And are collision attacks the only kind of attacks you need to guard against?

(If it matters, the context involves authors that publish messages to the general public, at a rate that may vary from hourly publications to a handful of messages in a month, and the general public needs to be able to tell those messages originate from those authors.)

No it's not useful to use slow hashing in such a situation.

The relevant attacks against the hash in a digital signature are second pre-images and sometimes collisions. Assuming the hash-function is secure, then there is no way to find collisions with less work than $2^{n/2}$, and second pre-images with less work than $2^{n}$. There is no weak part the attacker can abuse in his attack, so he needs to face the full strength of the cryptographic hash.

As long as the algorithm remains unbroken, we can make the problem exponentially difficult for the attacker, while increasing the cost only linearly(or something similarly low) for the defender. In short we don't fear high computational power, we only fear crypto-analysis.

With password hashing, the relevant attack is a first pre-image. The problem here is that typical passwords have a low entropy, i.e. they're easy to guess. When guessing the original password the attacker doesn't care how strong the hash-function is, he simply executes it with many different inputs. We use slow hashes here, to increase the effective strength of the password by perhaps 20 or 30 bits.

There is no way to slow down the attacker exponentially while slowing down the defender only by a little bit. That's because the attacker has the same knowledge as the password verifier, and does exactly the same thing as the verifier. Any slowdown hits the defender just as much as the attacker.

The only thing we can try is to minimize the advantage an attacker gets from specialized hardware, and make the hashing as slow as the defender can afford. This is a desperate measure that's only used because no good defense is available.


RSA accumulator exclusion proof without set In researching about RSA accumulators I came across this question, Inclusion and Exclusion proofs in RSA accumulators - from the first answer I had assumed that proof of non-membership could be computed without knowledge of the set, i.e. using only the accumulator value itself ($A$), and the element ($x$) not contained in $A$. This is accomplished with Bézout's coefficients $ax+bu=\gcd(x,u)=1$, the proof is $\pi=(^{},)$, verification is checking $(g^{a})^⋅^{}=g^{ax+bu}=$. If adding a member then proof of membership can be done without the set also.
When I revisited this after looking at a few implementations I realized the implications,  is the product of the accumulated elements, and therefore although the individual set members are not required, this product is, and it could potentially be a huge number with many accumulated elements, and therefore storage or communication of  might be infeasible quite quickly, as compared to the accumulator itself which uses modular exponentiation.
Have I missed something? Is the exclusion proof possible without the set? I ask as I experimented with say 1,000,000 set members, each with a hash to prime computed for it, e.g. Blake256, and quickly realized that not only is  hard to store and communicate with an increasing number of elements but it would take forever to calculate the product of those primes, so in effect, proof of non-membership without knowing the set is only possible with a small number of accumulated elements (providing this product can be communicated and stored)?
If the above is the case, then is there another tool, accumulator, or otherwise, where an exclusion proof is possible without possessing the set members (or the product), or is this fundamentally not possible?

Great observation! Just a quick recap: $A=g^u\bmod{N},$ where $A$ is the accumulated value, $u=\Pi_{i\in S} x_i$, is the product of the accumulated values $x_i$, where $x_i\in S$ and all accumulated values $x_i$ are primes. An exclusion proof of $x$ is a pair of group elements, $\pi=(g^a,b)$ such that $ax+bu=1$, using the Extended Euclidean algorithm, since $x\notin S\implies (x,u)=1$.
There are essentially two possibilities with respect to generating the exclusion proofs in an RSA accumulator.

The factorization of $N$ is known

This might occur in some use cases if there is an authority who manages the accumulator, e.g., in the Accumulator Manager setting, see this work for an example. In this case $u\bmod{\phi(N)}$ is computable since $\phi(N)=(p-1)(q-1)$ is computable from the factorization of $N=pq$. You can imagine that the Accumulator Manager periodically updates/publishes $u\bmod{\phi(N)}$ to facilitate to efficient exclusion/inclusion proof generation for its users. Therefore, in this centralized setting the mentioned problem does not occur as the bit length of $\log_2(u)\approx\log_2(\phi(N))\approx\log_2(N)$.
Note that even though the exponent $u$ might be large, the Accumulator Manager can convince its users that given $N,g$ and $u$ the exponentiation $g^u\bmod{N}$ was computed correctly without disclosing its users the factorization of $N$. Efficient proofs of exponentiation protocols were proposed by Pietrzak and Wesolowski.

The factorization of $N$ is unknown

This is the tricky setting! Let's assume that there are $n$ accumulated elements, i.e., $\vert S\vert=n$. Then, the size of $u$ is $\log_2(u)=\sum_{x_{i}\in S} \log_2(x_i)=\log_2(p_n\#)$, where $p_n\#$ is the $n$-th primorial. Just to illustrate the growth rate of primorials, $\log_2(p_{2021}\#)=25151$, that is roughly $3.07$ KiB. Unfortunately, $u$ cannot be reduced $\bmod{\phi(N)}$ since the factorization of $N$ is not known. You were not missing anything, if we were in this setting, then unfortunately the RSA accumulator is not efficient to store thousands of elements.
Are there any accumulators that do not require the knowledge of the full set for computing exclusion proofs ?
The simplest example could be a sorted Merkle-tree used as an accumulator. In a sorted Merkle-tree leaves are sorted according to some ordering. In the case of sorted Merkle-trees, computing the exclusion proofs do not increase linearly in the size of the accumulated set, rather logarithmically. With 2 inclusion proofs of neighbouring leaves, a prover can show that a certain leaf between those elements is not contained in the sorted Merkle-tree.


With DES, is ECB encryption mode equivalent to CBC with null IV for short data blocks? I got to this by experimentation, but can someone maybe provide an explanation for this?

The CBC mode processed as $c_i = E_k(p_i \oplus c_{i-1})$ with $c_0 = IV$
The ECB mode processed as $c_i = E_k(p_i)$

If you set the first block with $$c_o = IV = 0$$ in the CBC mode, than it is calculated as $$c_1 = E_k(p_1).$$ This is exactly as ECB mode.

The next blocks, however, will not be equal;

in ECB mode $$c_i = E_k(p_i)$$
whereas in CBC mode $$c_i = E_k(p_i \oplus c_{i-1}) \neq E_k(p_i) \text{ for } 1 < i \leq m$$ where $m$ is the number of blocks.

Therefore the equality is only valid for the first block.


What restrictions exist for publishing on strong encryption in USA? In the past, there were export and other restrictions on publishing information, source code or otherwise making new strong cryptographic items available without prior government approvals.

There are many conflicting regulations, laws, constitutional freedoms like freedom of speech and various legal precedents that make this area confusing; ITAR, EAR, etc.

So my specific questions are, are there still legal or regulatory restrictions for U.S. citizens that prohibit our ability to publish papers and articles about strong encryption techniques, improving existing techniques or introducing new cryptographic methods?

How about publishing source code accompanying such papers which are made publicly available? Is that still considered “exporting” that requires approval?

Edit1:
That’s helpful guidance on software/hardware items.
What about simply publishing research papers about improving and supplementing existing algorithms like AES, ChaCha, etc. without actually shipping anything other than a published paper?

My experience is from my time working in the State of Georgia, and firstly, how true that you want to stick to this depends on your funding source, and your end goals.

For software, the truth is probably nothing needs to be done in a practical sense due to Bernstein v. USA, but it's legally more complicated, and the details are here.
By the letter of the law: If your keys are greater than 64-bits, each time the cryptographic functionality of the source code is updated or modified you have to notify NSA and the U.S. Department of Commerce Bureau of Industry and Security (BIS).  If there are changes, you will need the specifics to notify BIS and NSA.  I also explicitly keep embargoed countries and people from accessing the files because I only distribute them on request.  This means that you can do whatever, and then publish the source code if you notify BIS.  I also send them updates every 3 months to say "nothing has changed" because if not, they ask.

For hardware, it's much more complicated because it is much more inconvenient.  I cannot fab anything without the proper forms in place, and the fabs enforce this as well.  I need a product ECCN.  Another annoyance is that I always end up making "hardware for export" for conferences.  For example, I have a power attack for SIMON128/256, but I've only shown the SIMON32/64 attack publicly because there's no way to guarantee who's in the audience.

The biggest issue of why to care is the funding source.  If you get USA money, you want them to feel like you are playing by their rules.  I've put up with the bureaucracy so I've been able to get repeat funding for semiconductors, and those aren't cheap.


How are Zero-Knowledge Proof protocols designed? There are some classic ZKP examples out there (the alibaba cave, the colored balls, etc. See the Wikipedia page for details)

To me it looks like these protocols were invented "ad-hoc". That is, someone came up with a clever solution for that particular problem, and it's not immediately clear how it applies to other problems.

Is there a more "direct" way of coming up with a protocol? Are there situations where a ZKP is not possible?

Any statement that is checkable in P (i.e., any NP statement) can be proved in zero knowledge. This can be shown by giving a ZK proof for any NP-complete problem --- historically, 3-colorability of graphs or Hamiltonian cycle. But giving a reduction to these graph problems might seem artificial. Perhaps a better approach is to use an NP-complete problem like circuit satisfiability, which is what is suggested in:

  Marek Jawurek, Florian Kerschbaum, Claudio Orlandi: Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently. ACM CCS 2013.

I don't know if you'll necessarily consider this more "direct", since it is only direct if you already know about oblivious transfer and garbled circuits.

Even the toy examples from wikipedia have aspects that are fairly standard to many ZK proofs: in particular, pre-commitment to some answers, a randomized challenge, and amplification.

Another good example of a not-so-cryptographic ZK proof is the graph non-isomorphism proof.


Certificate == signed public key For primes p and q used to create a keypair, I understand that the following operation is used to create a signature:

$M^d (\bmod\ N)$

where d and N have their usual meanings and M is the message. In this case, however you need to possess the public key in order to verify the signature S as follows :-

$S^e (\bmod\ N)$

In the case of a certificate (CA signed or self signed), is the plaintext public key part of it?

To sign a message $M$ under RSA, one should NOT build the signature as $\mathcal{Sign}(M)=M^d\bmod N$, for several reasons:

either that limits to messages $M$ in range $[0..N-1]$, or that allows forgeries of the form $\hat M=M+k\cdot N$, because $\mathcal{Sign}(\hat M)=\mathcal{Sign}(M)$;
that allows forgeries of the form $\hat M=R^e\cdot\prod{M_j}^{a_j}$ because $\mathcal{Sign}(\hat M)=R\cdot\prod{\mathcal{Sign}(M_j)}^{a_j}\bmod N$.

For some safe ways to use RSA to build signatures, see PKCS#1 or ISO/IEC 9796-2 (the first signs short messages only, therefore it is customary to use it to sign a hash of a message, rather than the message; the second always use a hash).

Public key certificates are signed messages including a public key, and additional informations usually including the identity of the legitimate holder of the corresponding private key, the identity or/and reference of the signer,  the rights of the holder of the private key...


Multivariate cryptography - easily invertible quadratic map I am reading through multivariate cryptography and in every source I have seen, the secret map $P$ is described as "easily invertible" or "easy to invert".

What exactly does it mean "easily invertible"?

Normally a multivariate scheme has a central private polynomial map that transforms linear multivariate polynomials into non-linear multivariate polys. This map has to be (easily) invertible, this is, it must allow the owner of the map to recover the original input linear polynomials.

Then define the composition of maps found in a scheme based on MPKC as following:

$$P(p_1(x_1,\ldots,x_n),\ldots, p_n(x_1,\ldots,x_n)) = T \circ \mathcal{F} \circ S(x_1,\ldots,x_n) $$

Or in a simplified version where $X$ denotes the $n$ variables on $x$ and $\varphi : \mathbb{F_p^n} \to \mathbb{F_{p^n}}$:

$$P(p_1(X),\ldots, p_n(X) )= P(X) = T \circ \varphi^{-1} \circ \mathcal{F} \circ \varphi \circ S(X) $$

As you may know, the public key $P$ consists of $n$ multivariate non-linear polys so when Bob substitutes for $x$ and sends the output $Y$ of $P$ to Alice, she inverts the composition of maps, then:

$$P^{-1}(p_1(X),\ldots, p_n(X) )=P^{-1}(Y) =S^{-1} \circ \varphi^{-1} \circ \mathcal{F}^{-1} \circ \varphi \circ T^{-1}(Y) $$

Obviously, both transormation matrices $T,S \in F_q^{n\times n}$ must be invertible , and the central private polynomial map must be too in some way (trapdoor or root-finding over $\mathbb{F_q}$), recovering the initial values for $X=(x_1,\ldots,x_n)$ that Bob had chosen.

I recommend you to check the Matsuomoto-Imai MV-scheme since it uses the Frobenious Automorphism over $F_2$. There you can learn the insight behind this kind of schemes and procceed to the original version of HFE wich uses the principles of Mat-Imai.


ECB weakness and its exploitation Lets say that I have a server which encrypts information at the server side using ECB mode with the blocksize of 16. If the server appends data that I control with a secret and sends back the ciphertext, it is possible for me to figure out what the secret is, by bruteforcing one character at a time.

Now lets consider a scenario where there is some secret data(say A) being prepended to my data(whose length I'm unaware of). There is also some some other secret data(say B, whose length I'm also unaware of) appended to my data. This is then encrypted and sent back over to me. Is there any way I can figure out what "B" is?

Yes, this is easy enough to exploit.

Start by sending any 15-byte message $m$, and then 256 different 16-byte messages consisting of $m$ followed by each of the 256 possible values of the last byte.

One of the encrypted 16-byte messages will have the same first ciphertext block as the encryption of $m$.  Find out which, and you've found the first byte of the secret!

Now, can you figure out how to repeat this to find the second byte of the secret, and so on?

For the second task, start by figuring out the length of the secret prefix.  How would you do that?  (Hint: Try changing the first byte of your message and seeing which ciphertext block changes.  What does this tell you?  How would you figure out the length of the prefix more precisely?)