What is the difference between a dual cipher and a tweak? I have looked at the idea of dual ciphers but I cannot convince myself I really understand them. I think I just need a very simple worked example.

I was given the definition:
Two ciphers $E$ and $E′$ are dual ciphers if they are isomorphic, i.e. if there exist invertible transformations $f(⋅)$, $g(⋅)$, $h(⋅)$ such that $\forall \ P$ and $K$ $$f(E_K(P))=E′_{g(K)}(h(P))$$
However, this is not easy for me to follow. I think $E$ is the encryption method (in my case below, $[(P \times K_1)+ K_2] \bmod26$). Yet looking at the definition it seems $f(.)$ is the cipher, is that right? And $P$ and $K$ are the plaintext and cipher key respectively. But I really don't understand what $g(K)$ and $h(P)$ are, or how to derive them.

Let's say my encryption cipher is: $C = [(P \times K_1)+ K_2] \bmod26$

How do I make a dual cipher of it? A very simple one is fine. If my cipher is not suitable, would you give an equally simple one that can have a dual cipher?
In my dual cipher from $.1$, what are my $g(K)$ and $h(P)$?
What could I do to this cipher to makes it a tweak but not a dual cipher?
How do I show my tweak is not a dual cipher?

This has been bugging me for a while so a simple example would be very much appreciated. I have posted similar questions but the answers are too difficult for my age and level.

For distinct tweaks $t \ne \tau$, the ciphers $E_{k,t}$ and $E_{k,\tau}$ should appear to be independent uniform random permutations for uniform random $k$.  For example, you could think of it like having a single-bit tweakable block cipher where $E_{k,0} = \operatorname{AES256}_{k_0}$ and $E_{k,1} = \operatorname{Serpent256}_{k_1}$, where $k_0$ and $k_1$ are like magic independent uniform random bit strings somehow both deterministically derived from $k$.

For dual ciphers $E \ne E'$, $E_k$ and $E'_k$ are very much not independent—there is a deterministic relation between them for every $k$, namely $f(E_k(p)) = E'_{g(k)}(h(p))$ for some deterministic functions $f$, $g$, and $h$.


Periodicity of hash functions Consider the naive hash function: HASH = INPUT % 4. This function is periodic in the sense that if we call it with sequential numbers 0, 1, 2, 3, 4, 5, ... the produced hashed sequence will have periodicity of four: 0, 1, 2, 3, 0, 1, 2, 3, 0, ....

My question is whether modern cryptographic hash functions, such as SHA256, are periodic in this sense? In other words, are there some integers 0 <= n and 0 < k such that HASH(n + b) = HASH(n + b + ak) for all integers b in [0, k - 1] and all positive integers a? For example, will the sequence SHA256(0), SHA256(1), SHA256(2), SHA256(3), ... be periodic after some point?

One of the purposes of Hash function is, of course, to make collisions unlikely (both of the deliberate and undeliberate kind). With periodicity this would be broken. However, to avoid collisions in practice, we only need that n and/or k are (very) large and unknown. Has it been proven that no n and k exists?

(This question was previously asked on Stack Overflow.)

What you're actually looking for is called the cycle length most of the time in cryptography.

For a random mapping $f:\{1,2,\ldots,k\} \rightarrow \{1,2,\ldots,k\}$ the cycle length is expected to be $\sqrt{\pi k/8}$ and the tail length is expected to be the same.
If you want more details and some fancy illustrations, the Handbook of Applied Cryptography (PDF) has them.

If you model a cryptographic hash function as a random mapping (which you do most of the time), then you'd expect a cycle length of $\sqrt{\pi 2^n / 8}=\sqrt{\pi}\cdot 2^{\frac{n-3}{2}}$ which is $\approx 2^{127.325748064736}$ for $n=256$, which is the case for SHA-256.

So the TL;DR is:
No it has not been proven that no such $n,k$ exist, but chances are that they exist and range in the area of the values I showed above, which are of no practical relevance as of today.


Shamir's ID based signatures - Notation issues I am currently implementing Shamir's ID Based signature scheme as defined in the original paper (archive link). The sign and verify operation are defined as follows:

Sign: $s = g * r^{f(t,m)} (\mod n)$

Verification: $s^e = i * t^{f(t, m)} (\mod n)$

I have some troubles to convert this to Java code, because I am unsure about the order of evaluation, i.e., I am unsure, what the modulus refers to in this context, the hole right hand side (including the multiplication) or the exponentiation operation, only?

PS: This post is related to this question.

Ok, lets look at the operations.

Sign: $s = g * r^{f(t,m)} \pmod n$

This is an assignment. You compute $(g * r^{f(t,m)}) \mod n$ and assign the resulting value to $s$. If you have a multiplication $(a \cdot b) \mod n$, this is equal to $((a \mod n)\cdot (b \mod n)) \mod n$. See for instance here.

Verification: $s^e = i * t^{f(t, m)} \pmod n$

This is no check for equality, but a check for congruence.

You can implement this by computing $s^e \mod n$ as well as $(i * t^{f(t, m)}) \mod n$ and check if these values are equal.

fgrieu has recently written an answer to a recent question on congruences which clarifies this nicely.


What is primary security in ECC? I read the following paragraph in a book about Elliptic Curve Cryptography, but didn't understand it:

  The primary security in ECC is the parameter $n$; where $n$ is Order of point $G$, that is $n$ is the smallest positive integer such that $nG = O$, where $G$ is a base point represented by $G= (x_g, y_g)\ on\ E (F_P)$

What does that mean?  Does a larger $n$ value imply a higher security level?

Take a point $G$ on the elliptic curve $E$. Someone calculates point $P = h*G$ where $h$ is some secret number (this can be done with point addition and duplications fast). Your task: Given public points $P$ and $G$ and curve $E$, find the secret $h$.

Solving this problem is hard. That is the problem that makes elliptic curves secure.

  Does a larger n value imply a higher security level?

Yes, the $n$ in your explanation is the order of a point on a curve, or put another way, it is the number of times you have to add the point to itself until you end up with the point at infinity $O$.

(There is also the order of the group of points on $E$ which is simply the number of points on the curve. Don't confuse these two orders, they are not the same thing).

Having a point $G$ with high point-order $n$ implies that the group has at least order $n$ as well.

So why do you want to pick a point with high order $n$?

The reason for this is, that if you pick a point with low order, there is a mathematical way that allows an attacker to solve the elliptic curves discrete logarithm problem faster. This is known as the MOV attack on elliptic curves:

http://www.cs.rit.edu/~txb7419/Crypto/MOVAttack.php

Note: If you play around with curves (something I suggest you should do), you will find that some points can have a scary low order. I did some experiments with a toy curve in the past:

$y^2 = x^3 + 1001*x + 75$, modulo prime $p$ = 7919

This curve has group order 7888.
If you examine the points on this toy curve (you can brute-force everything) you'll find most of them have point-order 7888 as well. Point <4023, 6036> is for example one of them. The point with the lowest point-order I've found on this curve is <7285, 14> with order of just 6.

Due to the MOV condition the second point would be a very bad point choice as G on this curve.


Is there any practical use of reduced rounds of AES There are lots of attacks which are on reduced block ciphers. There are practical attack on five rounds of AES-128five rounds aes broken in six minutes. I was just wondering if there is any practical application of reduced rounds of AES where less than 10 rounds are used.

There is not much use for reduced-round AES as a block cipher per se. AES has been carefully designed to provide appropriate security margins and 20 years of cryptanalysis show that they are just right - reducing the number of rounds would make it potentially susceptible to attacks.

On the other hand, the single round function is a very useful transformation that provides good mixing and other provable properties. Moreover, widespread hardware support for the round function (like AES-NI instructions and similar) makes it attractive from the performance point of view.

A good example is a lightweight hash Haraka designed for short-input hashing that uses AES round function.


Using the security definition in the malicious model to prove security in the semi honest model Can I use the security definition in the malicious model in order to prove the security of a two-party protocol which is in the semi-honest model? (I am using IDEAL/REAL Model paradigm)

Would you please explain it to me?

These definitions are from "Efficient Secure Two-Party Protocols-Hazay-Lindell"
Definition 2.3.1 (Malicious model)

Definition 2.2.1 (Semi honest model)

-

No, you cannot do this, because, as explained further in the book, security against malicious adversaries does not imply security against semi-honest ones.


Key strenth in Cipher cascades (Veracrypt) Disclaimer : basic crypto knowledge

So this is a question specificly about veracrypt , but theoreticly applies to any other encryption software which supports cipher cascades .

So if you use a cipher cascade with 3 cipheres e.g : AES(TWOFISH(SERPENT)) , then the key is divided in 3 different keys (hashes from KDF ) with 1/3 of the original key strength . So like a 8-10 charakter long password would not be considered secure right ?

But what if you use a keyfile like some mp3 file or some random generated stuff like an RSA cert. Veracrypt uses the first 1024 byte of the file so that would make a 4096 bit master key and a 1365 bit key for every cipher in the cascade if I understood that right.  Which would be more than enough to be secure right?

Please correct every misunderstanding in my previous claims.

What you would do in such a case is take a master key (which could be derived from a password) of a certain length (in your cases probably 128 or 256 bit long) and use a key derivation function (like HKDF) to derive three distinct keys of equal length which can be used in one algorithm each.

This way, each of the encryption keys will have the same strength as the original masterkey and the leakage of one of the encryption keys won't affect the other ones.

  Veracrypt uses the first 1024 byte of the file so that would make a
  4096 bit master key and a 1365 bit key for every cipher in the cascade
  if I understood that right.

Just taking 1024 byte of some file will yield something with the length of 8192 bit, but the key won't have a security level of that size, since the data you are using is probably not uniformly distributed.


Challenge Response Authentication - Client Generating Challenge Let's say we have a client (the not trusted party) and the server(wants to verify that the client is who he claims to be.

The client has access to both the private key and the public key, whereas the server only knows the public key.

Question
Instead of the server being responsible for generating the challenge, would it be as safe if the the client himself generated a random challenge and later signed it (so that the server could later verify this). Is there a weakness in RSA that would make this scenario bad?

NOTE
The public/private key pair will only be used once, and will be re-generated each time.

The attacker can use replay attack, i.e, he/she can replay a challenge that is signed by the user in the past(which is used as a challenge to server) and can send this as a nonce to the server. To avoid this, server generates and sends the challenge.The idea works if server maintains a list of previous nonce used but this has its limitations on practical implementation.

Hope this helps.


Test Vectors for XEdDSA Anyone aware of test vectors (preferably with intermediate values) for the XEdDSA algorithm?

Open Whisper Systems' own curve25519-java repository has a few test vectors in the code in android/jni/ed25519/tests/. From xeddsa_fast_test(), you get this test vector in particular:

Private key is all zeroes except byte 8, which is set to 189, and then clamped and the private key generated from there
The message is 200 bytes of zeroes
The random bytes are 64 bytes of zeroes
The resulting signature of this should be the byte sequence 11c7f3e6c4df9e8a5150e1db3b30f92de3a3b3aa438656545fa7390f4bcc7bb26c431d9e90643e4f0eaa0e9c557766fa69ada576d63dcaf2ac326c11d0b97702.

Incidentally, XEdDSA as specified has been found not to mitigate sufficiently well against differential power analysis. If the only reason why you're interested in XEdDSA is only mitigation of power-analysis attacks, you may want to look into the Internet Draft draft-mattsson-cfrg-det-sigs-with-noise-02 instead, which took into account the aforementioned findings.


Decoding a message on elliptic curve Let's say I have an elliptic curve $E$ $y^2=x^3 + 486662x^2 + x$ over a prime field $GF(2^{255} - 19)$. My algorithm for computing $E(m)$ is as follows:

I take the bits 1 through 32 of the message and plug that for $x$ in the equation.

I then calculate the result, store it as $x$,

and calculate the sign of $y$ using the first bit of $m$.
Let $e$ be the encryption key, then we can set the encrypted value of $m$ equal to $$Enc(m) = E(m)^e.$$

My question is how can I decode the message if I know the encryption key? Is it always possible?

if your $e$ is coprime to $p-1$ where $p=2^{255}-19$ you can calculate the $e$-th of an integer modulo $p$ which means you can recover $E(m)$ given $E(m)^e$. In fact, if the condition holds, there exist $u,v \in \mathbb{Z}$ such that $eu+(p-1)v=1$ (Bezout's identity). Now, we are looking for an integer $x$ such that $x \equiv a^{1/e} \pmod p$ i.e. $x^e \equiv a \pmod p$. It is easy to find it: $a^u \equiv x^{eu} \equiv x^{1-(p-1)v} \equiv x\times (x^{p-1})^{(-v)}\equiv x \pmod p$ because $x^{p-1} \equiv 1 \pmod p$ according to Fermat's little theorem.


Can Stream Cipher be Used to Encrypt & Decrypt a File (Eg: .txt .docx .exe .zip)? I was new to cryptography. And I know that in the world of cryptography there are two types of Symmetric Algorithms:

Stream Cipher (RC4, Salsa & Chacha)
Block Cipher (DES, AES)

And when doing some research on their implementation, I only looked at file encryption & decryption software products that use the AES algorithm (Block Cipher in general). (i know that AES is secure)
Can anyone help me answer the question whether Stream Cipher can be used to encrypt files like: .txt .docx .exe .zip?
I know this is a stupid question. Please forgive me.

Yes, for sure.
Commonly block ciphers are used for disk encryption algorithms because disks (or partitions) have a particular size. So there is no place to store an IV or authentication tag. They are also optimized for local changes to occur w.r.t. confidentiality and locality of the change. Finally they have to operate for a specific sector size. A stream cipher would be less useful here.
However, the size files can generally be changed in both length and content pretty easily. This application level encryption has much more freedom, so any cipher can basically be used. You should however remember that stream ciphers often use XOR, which means that you may loose confidentiality if multiple versions of the same file are available to an attacker and the IV wasn't changed. In other words, you'd have to fully re-encrypt the file each time a change needs to be stored.


Securely generating auth tokens (Disclaimer: I'm an experienced server-side Java programmer, but with little crypto experience.)

Objective:

I've got a login server which, given a login+password pair, should issue a unique auth token. Using the same login+password pair multiple times should issue new unique tokens, all of them should be valid at the same time. A token is a ciphertext that only the login server should be able to create. Everyone else should only be able to extract the payload from it.

Possible solution:

First, I thought I should just use RSA to encrypt the payload with the private key. Other parties would just use the public key to decrypt it. But I read somewhere that RSA cipher doesn't provide integrity and authenticity so I figured I need to add an RSA signature, so it'd look like:

RSAcipher-with-private-key(payload-length + payload + RSAsignature(payload))

Then I discovered that the plaintext cannot be larger than the key size and thus I need a symmetric cipher, so I went researching on AES and stumbled upon GCM. As I understand, GCM solves the A. and I. problems, so I wouldn't need the signature anymore, and came up with that:

RSAcipher-with-private-key(AESkey + GCMiv) + AES-GCM-cipher(payload)

So the other parties would extract the AESkey and GCMiv using the public key, and then use that to decipher the AEScipher block.

I'm using BouncyCastle java library, since some people say AES/GCM in Java 1.8 is broken.

Will that work, is that secure, am I trying to invent a wheel here? If that's the case, what out of the box solution I could use?

In asymmetric crypto including RSA, we ALWAYS encrypt with the public key, and decrypt with the private key (NEVER the other way around). In the question, what's wanted is to sign with the private key, not encrypt.

And that's enough to solve the whole problem, since RSA signature schemes exposed in BouncyCastle or the Java crypto API allow to sign data of arbitrary length.

Addition: The objective of encryption in modern cryptography is to prevent an adversary from gaining information about what's encrypted (with the exception of its length). When a piece of data is transformed into a cryptogram that can be returned to the original data using a public key, in such a way that only the holder of the private key could have prepared the cryptogram, that's not encryption; that's signature with message recovery.

In that name, signature covers that holding the private key is necessary to prepare the cryptogram, and that the private key allows to check the cryptogram. Message recovery covers that the cryptogram can be transformed back to the original message.

RSA signature schemes with message recovery (such as those in ISO/IEC 9796-2) have an advantage over those with appendix (such as those in PKCS#1): the size overhead for signing is smaller (slightly over a hash size, rather than a modulus size). For example, when using RSA-2048 and SHA-256, ISO/IEC 9796-2 embeds a 222-byte message into a 256-byte cryptogram, when PKCS#1 requires a 478-byte cryptogram (222 bytes for the message in clear, and 256 bytes for its signature).

As I understand it, the question attempts to make an hybrid signature scheme with message recovery, by mixing textbook RSA (used for signature with message recovery of a symmetric key), and AES/GCM (for integrity check and recovery of the bulk of the message). This is insecure to the utmost: an adversary (assumed to hold the public key, by definition of that) can determine the symmetric key from the RSA part, and then alter the message itself to whatever is desired.

Again, the problem at hand is finely solved with standard RSA signature. Appropriate schemes with appendix are directly available from the BouncyCastle or the Java crypto API. Message recovery could be used if reducing the size of the cryptogram by a few hundred bytes matters. While ECDSA signature (also readily available) would also reduce the signature overhead (to only about double that of RSA with message recovery), and significantly speed-up signature, it has the disadvantage that checking a cryptogram is significantly slower than with RSA.


Knowing the key, how do I decrypt the affine cipher? I have an encryption function

$$E(p) = (ap + b) \mod{26}$$

where the parameters are  $a=7$, $b = 10$, and $p$ is the plaintext letter.

I was asked to decrypt the ciphertext

LJMKGM

using this information.

So, I tried to solve in this way:

I wrote the letters and indexed them from 0 to 25.
For each indexed ciphertext letter, I used this function to decrypt $$D(c) = (ac-b) \mod{26}$$ where $c$ is the number that represents the ciphertext letter.

I know that the plaintext is "please". For the first ciphertext letter, my method works, but for the rest it doesn't work.. what is my mistake?

This is a special case of the affine cipher where $m=26$.

Let's encrypt a single letter using your $E$. Let it be m, say, which is at index 12. So, $$E(12) = (7 \cdot 12 + 10) \mod{26} = 16$$

Now if we try to use the $D$ in your question, we decrypt this as:

$$D(16) = (7 \cdot 16 - 10) \mod{26} = 24$$

which is obviously not right. The issue is that your $E$ and $D$ aren't really inverses. The general technique in math classes for finding simple function inverses is to swap the dependent/independent variables and solve, so let's do that to find the inverse for $E$.

Let $y = E(p)$ for convenience's sake. Now let's swap $y$ and $p$ in the encryption function (and swap over to modular arithmetic notation):

$$p \equiv ay+b \mod{26}$$

and try to solve for $y$ (aka $E(p)$). Well, we move $b$ over first, which is just your typical "Algebra" material from school.

$$p - b \equiv ay \mod{26}$$

Now here comes the kicker: you need to "divide by" $a$. Now, I don't know your abstract algebra background, but arithmetic modulo $n$ takes place in the ring $\mathbb{Z}/n\mathbb{Z}$, also sometimes written as $\mathbb{Z}_n$. The issue is that multiplicative inverses are not guaranteed to exist in rings. In the case of $\mathbb{Z}/n\mathbb{Z}$, an element $x$ only has a multiplicative inverse if $\gcd(x, n)=1$. Fortunately for us, $a = 7$ and $m = 26$ are coprime, so $a^{-1}$ does exist.

Hence, we can write:

$$a^{-1}(p - b) \equiv y \mod{26}$$

which gives us:

$$D(c) = a^{-1}(c - b) \mod{26}.$$

This agrees with Wikipedia's article on the affine cipher, so it's good to know that we're not totally off-track here. How do you find $a^{-1}$? The article Modular Multiplicative Inverse on Wikipedia gives you a few ways. In this case, I'd probably just try trial-and-error, but you can also use the Extended Euclidean Algorithm to do so if you dislike trial and error. Fortunately for us, someone at Princeton is hosting this modular inverse calculator, which tells us that $a^{-1} = 15$.

So, taking the above $E(12) = 16$, let's see if our new $D$ works:

$$D(16) = 15 \cdot (16 - 10) \mod{26} = 12$$

which succeeds! From there, I trust you can complete the computation for your ciphertext.


What is the difference between H(M) and H3(M, s, IDA)? What is the difference between H(M) and H3(M, s, IDA)?

I am aware of Hash function with a Message and a Key, but there are three parameters in:

H3(M, s, IDA).

Here M is the message, s is the key, and IDA is the identity of user A.
I meant that how to implement secure hash H3(M,s,IDA)

I'll take the (previous version of the) question as: how to implement a secure hash function $H3$ with 3 arguments, from one hash function $H$ with 1 argument, all with argument(s) in $\{0,1\}^*$.

Note: For a concrete $H$ with the destination set $\mathbb Z_p^*$ thought in the question, we could use SHA3-512 followed by a suitable function; for example, $x\to H(x)=g^{\operatorname{SHA3-512}(x)}$ where $g$ is a generator of $\mathbb Z_p^*$. That $H$ is collision-resistant to $\min\big(512,\log_2\varphi(p)\big)/2$ bits (where $\varphi$ is Euler's totient function); and first and second preimage resistant to $\min\big(512,\log_2\varphi(p)\big)$ bits. Further, it is secure in the Random Oracle Model for suitable choice of $p$.

The construction $H3(M,S,I)=H(\;M\;\|\;S\;\|\;I\;)$ where $\|$ stands for concatenation of bitstrings is such that usual security properties of $H$ (including collision-resistance and security in the Random Oracle Model) demonstrably apply to $H3$, if at most one of $M$, $S$, $I$ is of variable size.

Otherwise it is not secure in general: exhibiting a collision is trivial; for example, $H3(\text{01},\text{0101},\text{0101})=H3(\text{0101},\text{0101},\text{01})$. However, with the middle parameters $S$ random, secret, and non-malleable (as presumably in the question), there is no spectacularly practical attack.

A secure construction for variable-size inputs is $H3\big(M,S,I\big)=H\big(\;E(M)\;\|\;E(S)\;\|\;I\;\big)$, where $E$ is a prefix-free function on $\{0,1\}^*$ ; that is, such that
$$\forall X\in \{0,1\}^*,\forall Y\in \{0,1\}^*,\forall Z\in \{0,1\}^*,E(X)=E(Y)\|Z\implies X=Y$$
Examples of suitable prefix-free constructions for $E(X)$:

prefix each bit in $X$ with a $\text{0}$ bit, then append a final $\text{1}$.
prefix $X$ of length $b$ bits with $b+1$ encoded in big-endian binary (thus with $\lceil\log_2(b+1)\rceil$ bits starting with a $\text{1}$ bit), then prefix that with $\lceil\log_2(b+1)\rceil-1$ bits at $\text{0}$.
the encoding of bitstrings in ASN.1 DER then re-encoded into a bitstring (e.g. using big-endian conventions for internal consistency).


Are the asymmetric roles of the two keys in the elliptical curves the same (as for RSA)? Can they be interchanged indifferently? More precisely, and as for RSA, is it really true that it is not feasible to recirculate one of the keys knowing ONLY the other with the Elliptic Curves, as for RSA?  Or does ECs work differently on this issue? I mean only mathematically (I'm not talking here about OpenSSL's deceptive abilities to keep items in a file to facilitate public key regeneration).

In both RSA and usual¹ Elliptic Curve Cryptography (ECC), there is a public key and a private key, forming a matching pair. In signature, the private key is used for signature generation, and the matching public key is used for signature verification. In (usually, hybrid) encryption, the public key is used for encryption, and the matching private key is used for decryption. This dual role with exchange of usage order of the public and private key applies to RSA and ECC alike.
In RSA, it is additionally mathematically possible to exchange the values of the public and private exponents $e$ and $d$. It is thus possible to exchange the values of the public and private keys when expressed as pairs of integers $(N,e)$ and $(N,d)$. Such exchange of values is almost never done in RSA practice².
Such exchange of values is not possible in ECC. That's because an ECC private key is an integer $d$ in $[0,n)$ where $n$ is the order of the generator $G$ of the Elliptic Curve, and the public key is $Q=dG=\underbrace{G+G\cdots+G}_{d\text{ times}}$ where $+$ is the point addition operation of the Elliptic Curve group. The private and public keys are different mathematical objects, which values can't be meaningfully exchanged.

With ECC, given the private key, it is possible to deduce (calculate) the corresponding public key, unlike RSA.

Yes, under appropriate hypothesis: having the RSA private key in a non-standard format, and with an unusually large public exponent $e$.
In ECC, given the Elliptic Curve group³ and the private key $d$, it is a basic operation to find the public key: just compute $Q\gets dG$.
In RSA, when given the private key, it is not always possible to compute the matching public key. Specifically, when the private key is given in the form $(N,d)$, and the public exponent $e$ of the public key $(N,e)$ is a large random secret, finding $e$ is hard. However, finding $e$ is trivial when it is part of the private key, e.g. because the private key is in the recommended RSA private-key format in PKCS#1v2: $(N,e,d,p,q,d_p,d_q,q_\text{inv})$. And finding $e$ is easy when $e$ is below some threshold, e.g. $e<2^{256}$, which also is usual.

¹ As codified e.g. by SEC1.
² Such exchange is insecure if one of the public/private exponents $e$ and $d$ is less than $2^{256}$, which is common for performance reasons. Exchanging public and private key is secure only if the first chosen among public/private exponents $e$ and $d$ is selected at random in a much larger set, or if both are secret, negating the benefits of public-key cryptography.
³ Usually a public parameter, e.g. secp256k1 for anything Bitcoin. Common ECC groups are codified in SEC2.


Secure MultiParty Computation with secret inputs for secret outputs I want to know if it’s possible to use a SMPC (Secure Multi-Party Computation) to have $N$ entities compute the outcome of a known mathematical operation with two or more secret inputs, where each secret input is only known by one entity in the $N$-sized group.

I’m asking, because I want to define a protocol where two network nodes take part in a virtual money transfer – with $k$ witness nodes – where the balance of each node taking part in the transaction is kept secret to itself. After the transaction is calculated, each part can verify with the outputs whether the operation was successful or not.

Yes, that is possible -- that's exactly the problem that secure multiparty computation solves.  You should start by reading standard references on secure multiparty computation.

You might enjoy the following paper, and follow-on work:

Secure Multiparty Computations on Bitcoin,  Marcin Andrychowicz and Stefan Dziembowski and Daniel Malinowski and Łukasz Mazurek, IEEE Security & Privacy 2014.


entropy calculation in data wiping Can entropy being used as data removal verification in data wiping ? How we can implement the entropy calculation in a data wiping tool? The wiping tool will used overwriting method using single pass.

Your wording is rather off, "entropy" is not a verification algorithm, so it is impossible to use it as "data removal verification tool".

To test the (pseudo-)randomness it is possible to use any random data testing tool, such as the testing framework of NIST described in FIPS 140-2. It should be used at least on data filled with zero and the data after the wipe; in that case the original data cannot influence the result.

Note that the tool won't be able to distinguish between random data and data that was designed to look random. You will also need a rather large amount of data - so you cannot use this for single, relatively small file for instance.

Generally single pass overwrites are OK for modern storage devices, but the problem is that the data may be copied somewhere else before it gets overwritten. This is why you should e.g. use the secure erase function on modern SSD's and HDD's to be sure to get rid of the data. Or you can throw away the key of encrypted files so that the data becomes inaccessible rather than destroyed altogether.


Cryptographic Systems Involving Modular Exponentiation I am going through an "Introduction to Cryptography" chapter in my Elementary Number Theory course, wherein I'm studying cryptographic systems involving modular exponentiation.
The textbook (By David M. Burton) says that:

A user who wishes to conceal information might begin by selecting a (large) prime p to serve as the enciphering modulus, and a positive integer 2 < k < p - 2, the enciphering
exponent. Modulus and exponent, both kept secret, must satisfy gcd(k, p - 1) = 1. The encryption process begins with the conversion of the message to numerical form M by means of a "digital alphabet" in which each letter of the plaintext is replaced
by a two-digit integer. It is assumed that the plaintext number M is less than the enciphering modulus p; otherwise, it would be impossible to distinguish M from a larger integer congruent
to it modulo p.

Can someone please clarify the last line for me (in italics)? Possibly, by giving an example as to why will it be impossible to distinguish M from a larger integer congruent to it modulo p. What exactly happens when M is greater than p?

Can someone please clarify the last line for me (in italics)?

Ok, here is a very simple example of what can go wrong.
For a very simple example, let us consider $p=11$ (smaller than what they specify, however it'll act the same, and it'll keep the computations simpler), and $k=3$.
Suppose we want to encrypt the message $m=2$; what we'll do to encrypt is compute $m^k \bmod p$, in this case, $2^3 \bmod 11 = 8 \bmod 11 = 8$.  And, later on in the text, they'll explain how to decrypt.
However, to answer your question, suppose we were to try to encrypt the message $m=13$.  In this case, we'd compute $13^3 \bmod 11 = 2197 \bmod 11 = 8$.  That is, we got the exact same ciphertext that we did for $m=2$; that means that if we get the ciphertext $8$, we wouldn't be able to tell whether the original $m$ was $2$ or $13$ (and by default, we assume that it is less than $p$, namely, $m=2$).
It turns out that this encryption method always handles any $m$ the exact same way as $m+p$; hence if we get a message larger than $p$, there will always be a smaller message that encrypts the same way.
As a side note, when I computed $m^k \bmod p$, I wrote it out as $m^k$ and then applied the $\bmod p$ operation.  This works on these small toy examples, but on realistic cases, we convert the $m^k$ into a series of modular multiplications and squarings, and apply the modulo operation after each multiplication/squaring.  This is not related to your question - I'm just trying to anticipate a possible future source of confusion.


Why is RSA considered safe? Why is RSA safe, using this algorithm to calculate $d$ as the private key?
$$e\cdot d \equiv 1 \pmod{\varphi(n)},$$
where $e$ is part of the public key and $n$ is also part of the public key, so there is only one variable the attacker doesn't know, and that is $d$?  Why can't they can use the extended Euclidean algorithm to calculate it?  Even if they can't, why is it considered safe?

Yes, theoretically anyone can compute $\varphi(n)$ from $n$ and thus recover $d$ from $e$. This should be read as "given any $n$, it takes a finite amount of time to compute $\varphi(n)$".

More practically, "computing $\varphi(n)$ given $n$" and "factoring $n$" are equivalently hard. That is, if you can efficiently compute $\varphi(n)$ you can also efficiently factor $n$ and vice versa.

Now, if $n$ is sufficiently small, we can easily factor it and thus compute $\varphi(n)$ (which is what websites do), but as $n$ reaches cryptographically relevant values, it becomes infeasible (using current technology) to factor $n$ and thus to recover $\varphi(n)$.


Using xor encryption in the following use case I use an encryption scheme based on a symmetric cipher, with the corresponding symmetric key encrypted with RSA/OAEP using the public RSA key of the recipient.
I now want to use ECC crypto in replacement of RSA. Looking at the openssl API I can see that there is no RSA equivalent ECC encryption of a key, but only key derivation.
As the same symmetric key has to be encrypted for several different recipients, each of them owning its own encryption public ECC key, I can't directly use the derived key as the symmetric key.
So I am considering doing this:

create a "one time" ECC key pair,
derive a shared secret with this key and the recipient public key,
xor the symmetric key with the derived shared secret, ensuring that the latter is at least as long as the symmetric key,
sign the public part of the "one time" ECC key and transmit it along with the xor encrypted symmetric key so the recipient will be able to decrypt it.

I think that using xor encryption here is safe as:

the derived shared secret is supposed to be random looking and will never be reused, as one of the keys used for derivation is a one time key,
the derived shared secret is at least as long as the xor-ed content.

But maybe have I missed something?

It sounds like you're looking to implement something very similar to what was asked about here, with the addition of a signature of the ephemeral public key.  But as poncho's answer points out, the potential malleability of the XORed key and the ciphertext could potentially pose some problems.  The way the shared secret is derived may also introduce the possibility for issues here, though following the ECIES method with a KDF should help.
For the sake of differentiating this question from Maarten Bodewes's question, I'll assume you're more interested in replacing your existing scheme than implementing exactly what you've described.  One potential option to consider to using standard ECIES (using an ephemeral key and KDF to generate a new symmetric key) to encrypt the symmetric key of your original data.  This would certainly have both some computational and size overhead, but should achieve your goal.
Here you could still sign the ECIES output (or probably just the ephemeral public key) if that authentication is important to your system.  But if you can afford the overhead that might be a safer/less experimental approach.


advances in usability for cryptography/authentication I'm wondering if there have been any recent advances (say, the past 5-10 years) in human usability for cryptography and/or authentication?

By that I mean something that makes it easier for an average person to make use of the benefits of cryptography. It strikes me that although we have all these great algorithms for encryption and hashing, and they have widespread use in machine-to-machine communication, it's still hard for us humans to use cryptography, because there's an impedance-mismatch between these methods and the way most people's brains work.

(The only one I can think of is OpenID or things like it, namely a way of decoupling the authentication process from the point-of-use without compromising security, so that one authentication method can be used for many end uses.)

Some examples in case this doesn't make sense:

I was just reading the O'Reilly book "Web Security, Privacy, and Commerce" (2002 edition), and was reading about PGP, and wondering why after 20 years, it or something like it is still not in widespread use.

I'm also wondering why the allegedly secure websites (financial/healthcare) that I use, still use password access and still have "security questions" in case I forget my password, where the security questions aren't very secure.

This is an active area of research. There have been attempts at creating usable security tools and lots of user studies of existing tools (typically with critical results).

A good anthology for work in this area (a few years old now) is Security and Usability edited by Lorrie Cranor and Simson Garfinkel.

There is also a workshop every year called Symposium on Usable Privacy and Security (SOUPS) with lots of papers. However the best usable security papers tend to appear at the top security conferences (Oakland, Usenix Security, and CCS).


Reverse Java seed using outputs generated from nextInt(6)+1 Given a set of numbers within the range of 1-6:
[3,4,3,4,5,6,2,3,1,5,2,3,6,2,2,3,3,6,6,4,5,2,5,3,5,2,4,4,2,6,3,6,1,5,1,3,6,1,1,2,2,4,5,3,1,2,3,4,4,6]
generated using Java's nextInt(6)+1, is it possible to reverse engineer this to find the seed?
Upon investigating Java's source-code I understand this is how the nextInt() method works:
public static int nextInt(int n){
        if (n <= 0)
            throw new IllegalArgumentException("n must be positive");
        if ((n & -n) == n) // i.e., n is a power of 2
            return (int) ((n * (long) next(31)) >> 31);
        int bits, val;
        do
            {
                bits = next(31);
                val = bits % n;
            }
        while (bits - val + (n - 1) < 0); //do, until its a positive number
        return val;
    }

Since n in this case is 6, it is not a power of 2 so it carries out this part of the code:
do
  {
    bits = next(31);
    val = bits % n;
  }
  while (bits - val + (n - 1) < 0); //do, until its a positive number
  return val;

it now calls next(31) and this is the code where it essentially runs through a linear-congruential generator
public static int next(int bits){
  seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
  return (int) (seed >>> (48 - bits));
}

this 31bit number is returned as an int and assigned into bits
Finally we do bits % 6 and this gives the final value.
I have a few questions:
(1) what is the purpose of this line of code?
while (bits - val + (n - 1) < 0);
(2) How does one reverse engineer and find the seed from a set of numbers generated from this procedure?

what is the purpose of this line of code?
while (bits - val + (n - 1) < 0);

From a syntactic perspective, it ends the do opened above. From a functional perspective, it makes the pseudo-random number generated uniform on the specified interval. I'll focus on the later aspect.
Assume n was $3\cdot2^{29}\,$ (that is 3<<29) rather than $6$. After the statement bits = next(31); this quantity is uniformly random in $[0,2^{31})$. Therefore val = bits % n; is

bits with probability 75%; and then uniform on $[0,3\cdot2^{29})$
or bits-(3<<29) with probability 25%; and then uniform on $[0,2^{29})$

It follows that before the while, val is in $[0,2^{29})$ with probability 50%, in $[2^{29},3\cdot2^{29})$ with probability 50%. The second interval is twice as large as the first, and we see that val is very far from uniform on the whole interval $[0,3\cdot2^{29})\ $!
The while repeats the loop when in the problematic second bullet, and thus makes the outcome uniform on the full interval $[0,3\cdot2^{29})$.

Alternate explanation with small numbers
Imagine that, starting from $b=0$, four times: we double $b$, then add $1$ to $b$ if we get a tail from a fair coin throw. The outcome is $b$ a nonnegative integer less than $2^4=16$, and each of these $16$ integers is equally likely. That is, the outcome is a discrete uniform random number $b$ in $[0,16)$.
From this we want a uniform random number $v$ in $[0,6)\,$ just like nextInt(6) is tasked to do. Problem is, if we use a fixed assignment of values of $b$ from $[0,16)$ to values of $v$ in $[0,6)$, the outcome can't be uniform. The most even we can get is that $4$ values of $v$ have probability $3/16$, and the $2$ other $2/16$. Think of separating $16$ mints (the $b$) into $6$ persons (the $v$).
A simple solution to that is: when $b$ is in $[0,6)$, that's our $v$. When $b$ is in $[6,12)\,$, our $v$ is $b-6$. Otherwise, we try again, generating another $b$ using coin throws. That's what the code does in it's do … while loop, only with $2^{31}$ using next(31) where our analogy uses $2^4$ and coin throws; using bits for $b$, and val for $v$.

Off-topic: what's up with bits - val + (n - 1) < 0 ?
One wonders how while (bits - val + (n - 1) < 0); manages to do what's described above. bits is in range [0, 0x7FFFFFFF], n is 6, val is bits % n, thus val < bits holds and bits - val is non-negative. But it does not follow that bits - val + (n - 1) is non-negative, because the operations are carried per two's-complement arithmetic over 32-bit.
That's how int works in Java, many other computer languages, and most modern computer hardware when manipulating signed integers as a 32-bit quantities. If the int quantities u and v represent the integers $u$ and $v$, these integers are both in range $[-2^{31},2^{31}-1]$, then u + v is an int quantity representing an integer $w$ in range $[-2^{31},2^{31}-1]$ with $u+v\equiv w\bmod2^{32}$, that is by definition $u+v-w$ a multiple of $2^{32}$, and depending on values of $(u,v)$ that multiple can be $0$, $2^{32}$, or $-2^{32}$. In the end, $w$ is the integer $((u+v+2^{31})\bmod2^{32})-2^{31}$. That arithmetic is commutative, associative, has neutral zero, and every element has an opposite. A caveat: $-2^{31}$, that is -0x80000000, shares with zero the property of being it's own opposite.
So for example if bits was $2^{31}-2$, val is $0$, bits - val is $2^{31}-2$, bits - val + (n - 1) is $((2^{31}-2+(6-1)+2^{31})\bmod2^{32})-2^{31}$, that is $((2^{32}+3)\bmod2^{32})-2^{31}=3-2^{31}$, and that's negative.
For those that just want to move along: the condition bits - val + (n - 1) < 0 is logically equivalent to bits - val >= ((long)1<<31) + 1 - n (with no overflow and only non-negative quantities, thanks long being 64-bit).
It should now be apparent that bits - val + (n - 1) < 0 holds when bit is at the top of its interval [0, 0x7FFFFFFF]. It is left as an exercise to the reader to show that the rest of the interval contains a multiple of n integers, thus all the n values of val on exit of the loop are exactly as likely, under the assumption that all values of bits are.

How does one reverse engineer

That's already done. The question has reverse-engineered the algorithm, and even more than this: simplified the code from what it is in a recent Java environment by removing the thread-safety stuff (or traveling back in time to get the source before that was added); and thought about removing the part of the code that is demonstrably unreachable in the circumstance.

and find the seed from a set of numbers generated from this procedure?

Next step towards that goes: compute the probability that the condition in the while statement is true when n is $6$, and decide what can be done about this case.
Then proceed. There's several paths to resolution:

Brute force, trying all $2^{48}$ initial state values. This is feasible, but inelegant and resource-hungry.
Reducing the above search space by a factor of $6$ by exploiting the first result available.
Using that $6$ is even to get 18 bits of the seed out of 48 (with fair probability), then brute force the rest. That's relatively simple and educative. It's outlined in this answer of mine. Some combinations with the above tweaks work.
A that-could-well-work-but-I-didn't-bother-to-try approach using SAT solvers (in same answer).

Likely there are other approaches, but if there's anything readily applicable here or here, I missed it.
If stuck, state at what point at the bottom of the present question.


Sum of two squares problem I would like to know if there is any existing research on the following problem:

$$\text{For }a, b \in \mathbb Z \text{, given }n = a^2 + b^2, \text{output }a, b$$.

Searching for "sum of squares", "quadratic sum", "two squares", etc. on eprint did not return any related results that I could find. The problem itself may have been given a particular name, but if it has I don't know it and so I can't search for it.

I did a search on some of the math stackexchange sites and:

There appears to be a relation between a decisional variant of the problem and factoring. Namely, "determine whether or not $n$ is a sum of two squares" can be solved with knowledge of the factorization of $n$.
I found a result that allows the problem to be solved efficiently when $n$ is a prime congruent to $1 \bmod 4$.

The naive algorithm for solving the problem runs in time $O(\operatorname{sqrt}(n))$ by simply guessing all possible values for $a$ up to $\operatorname{sqrt}(n)$, squaring them, subtracting $a^2$ from $n$, then checking whether the result is a perfect square.

I would like to know any of the following:

Is there pre-existing research on the problem that I can consult

Does the problem have a name other than "Sum of two squares"

Can we prove that the problem is either "hard" or "easy", for the usual definitions of the terms on a hard instance of the problem (e.g. one where $n$ is not a prime congruent to $1 \bmod 4$)

A well-known result is $gcd(t+i, n)$ over Gaussian numbers where $t$ is a square root of (-1) modulo $n$. The reason is $t^2 = -1 \pmod{n}$ equivalent to $n | (t+i)(t-i)$ over $Z[i]$. Real and img components of this $gcd()$ are the squares.


Why does NaCL have different keys for signing and encryption? I want to start using NaCL to sign messages that will go into a message queue, and I noticed that it generates different keys for each operation. Is there a reason for this? Can I not use the same PK for signing and encryption?

The encryption part of NaCl is older. I think NaCl itself still doesn't have official signature support.

NaCl's box uses montgomery form public keys together with the montgomery ladder. This ladder only returns the x-coordinate of the result and thus is not compatible with most signature algorithms.

Ed25519 on the other hand uses (twisted) edwards form, with keys in the same format.

But it is possible to convert the keys between these formats (the missing sign of the second coordinate can cause some complications when converting from montgomery). There are several encryption products which use these conversions to share a key.
Using the same key for multiple purposes requires the algorithms to be jointly secure. Some people are not comfortable with that. Tanja Lange voiced some vague doubts at 30c3.

See Using same keypair for Diffie-Hellman and signing


Combining classical attacks and quantum cryptanalysis I'm regularly reading that AES-256 is secure against quantum computers because Grover's algorithm will only halve the key strength (i.e. "only" require $\sqrt{2^l} = 2^{l/2}$ operations instead of the full $2^{l-1}$ operations required to brute force the key).

However, would it be possible that classical attacks on symmetric ciphers such as AES could be sped up using quantum computing based algorithms? Is it possible / likely that the security of a block cipher is degraded more severely (e.g. by more than an additional 2 bits strength) if or when capable quantum computers become available?

The short answer is: Of course! Why not!

It is pretty easy to build an artificial secret key encryption scheme that is based on RSA and breaks if the adversary has a quantum computer*. Of course no one would want to build a symmetric primitive out of number theoretic assumptions as that would defeat the main purpose of being far more efficient than asymmetric crypto (the usual exceptions left aside...VSH...). However, symmetric primitives might provide exploitable structure that we just did not find yet. Indeed, in a far stronger security model where the adversary gets quantum access to honest parties (i.e., the CPA oracle) one can actually break several secret key encryption schemes as they are vulnerable to period finding algorithms. Therefore, the conventional effort of cryptanalyzing symmetric primitives has to be enhanced by the study of quantum algorithms.

[*] capable of running Shor's algorithm, which breaks RSA.


Is this SHA256 hash implementation secure from rainbow table, brute forcing attacks? So I have an implementation where by we have an $8$-byte random input (entirely random, not user defined) which we hash with $\text{SHA256}$. The hash is shared with many parties to the point that we consider it is effectively public, so we are concerned with potential attacks to reverse the hash.

With this input, there are $1.8 \times 10^{19}$ hashes.

So my calculations for brute-force feasibility are done taking into account reported hash rates of bitcoin mining rigs and ASICs from:

https://en.bitcoin.it/wiki/Mining_hardware_comparison
Current best $7,722,000$ MHash/s would take 27 days ($\frac{1.8 \times 10^{19}}{7722000000000  \times 60 \times 60 \times 24}$).

https://en.bitcoin.it/wiki/Non-specialized_hardware_comparison
Current best $2,568$ MHash/s would take 227 years ($\frac{1.8 \times 10^{19}}{2568000000 \times 60 \times 60 \times 24 \times 365}$).

Also, I'm assuming that since bitcoin mining is $\text{SHA256}(\text{SHA256}(x))$, that either the times above could be roughly halved, or in the case of an ASIC which may not be flexible enough to do single hashing, a brute force attempt would simply target $\text{SHA256}(target_{hash})$ instead?

As for calculating the rainbow tables, I'm guessing at the basic level, each record would be $40$ bytes ($8$ byte input + $32$ byte hash), leading to $1.8 \times 10^{19} \times (8 + 32) = 7.2 \times 10^{20}$ bytes $= 720,000,000$ terabytes

I've made a number of brain farts in getting to these numbers, so I'm not entirely confident in their accuracy, and whilst I've read many articles on the related topics, my concern is that they all seem to target password cracking, and therefore don't assume that $8$ bytes input is actually $8$ bytes of entropy, especially since they often promote dictionary attacks.

Please can anybody confirm the accuracy of the above numbers and whether my methods are sound?

TL;DR: 64-bit entropy is nowhere near enough against a serious attacker.

Yes, you have calculated the worst case correctly.
Your second calculation isn't about rainbow tables, but about a full hash table.

Now for "how long can you stop a serious attacker" if you hash a fully random 8 byte string with SHA-256. If the attacker has enough money, they can design their own ASICs for this or ask nicely at companies like AntMiner to produce such ASICs. So assuming you pay a little more, you can probably get 1GHash/s for 1000 USD (AntMiner's S7 is at 4.7THash/s for 575USD + energy, network,... at the moment). So to break the hash using one miner (with 1THash/s), you need 213 days, whereas if you buy 427 of them, you can break the hash in at most half a day and expect to break it in a quarter of a day on average and at this point you wouldn't even be egligible to the highest discount they offer (at 500 pieces and more).

Rainbow tables should allow for quick breaks of the security and normally reduce the storage required to $2^{2n/3}$ and the computational requirements to $2^{2n/3}$ per look-up or more generally, given $2^m$ storage, the lookup time will be around $2^{2(n-m)}$.
If you want to defend against rainbow tables, salts are inevitable, because you need a full rainbow table per unique salt, which is computationally and storage-wise intense. As for the efficiency of rainbow tables, you need a full pass over the complete space (all $2^{64}$ values) to build the table. For the original (first) publication of rainbow tables, see "Making a Faster Cryptanalytic Time-Memory Trade-Off" by Oechslin (PDF)


Why are NaCl secret keys 64 bytes for signing, but 32 bytes for box? Ed25519 secret and public keys can both be represented in 32 bytes. Why does NaCl use 64 byte signing keys?

Opening and sealing a box involves your private scalar and the other party's public key. So the private key is simply the private scalar.

Signing with Ed25519 involves your private scalar and your public key (to strictly bind the signature to that key). Since computing the public key from the private scalar is expensive, NaCl chooses to store it as part of the private key.

An Ed25519 private key consists of a 32 byte seed (from which you can cheaply derive the 32 byte private scalar and the 32 byte hash prefix) and the 32 byte public key.

Different Ed25519 implementations chose different private key formats, Brian Warner's blog has the details.


Tiger Tree Hash vs generic Merkle Tree Is there any advantage of using Tiger Tree Hash over any other hash function organized as the Merkle tree? Are there maybe any properties of TIGER that, say, SHA-2 or BLAKE in Merkle tree do not have?

And in general, is there any point of chosing Tiger Tree Hash over anything else in modern applications for file sharing purposes?

The Tiger hash function was mainly a notable thing back in the days as it was designed to make efficient use of 64 bit processors.

Besides some other uses, Tiger was (and sometimes still is) often used for file integrity verification purposes in file sharing proggies, by using the Tiger hash function to build a Merkle tree… resulting in a so called “Tiger Tree Hash”. (The main advantage of such a tree is that you can verify the integrity of each subtree, even when the data is not yet completely available… as it happens – for example – when downloading torrent files).

Personally, I don't see many advantages to SHA-2 or BLAKE. Especially, since Blake etc. were also build with an eye on efficiency when it comes to 64 bit processors – which are somewhat standard for desktop computers et al nowadays.

As CodesInChaos already indicated, the only reason to use Tiger at all would be compatibility with existing protocols. For new protocol designs, I personally would skip looking at Tiger.


Is SHA-1 still practically secure under specific scenarios? It is conjectured that SHA-1 has been broken from the "research" perspective but no in real world. That is that there is an algebraic attack that explores weaknesses on its algebraic construction. The same happens for MD5 but MD5 has been practically broken by finding collisions in real world. Can we still use HMAC with SHA-1 and be secure against preimage, second preimage and collisions?

I would recommend phasing out SHA-1 in any scenario where collision-resistance of a hash is required, for there is a wide consensus that an attack with $2^{69}$ complexity would work, it would already be feasible by a resourceful entity, and attacks only get better.

I'm still confident that SHA-1 is preimage and second-preimage resistant for all practical purposes in the foreseeable future, when its full output is used. Nevertheless, I would prefer SHA-256 or RIPEMD-160 when they are possible options.

I'm still confident that HMAC with SHA-1 is secure in any scenario where HMAC's key is assumed secret, for all practical purposes in the foreseeable future; this is because an improved security argument for HMAC remains valid with weak assumptions on the underlying (round function of the) hash. I could recommend it in a MAC application where using a tarnished name is not an issue, and speed matters.

Update: A collision for SHA-1 was published in February 2017 (4 years after this answer was written). It took an effort comparable to $2^{63}$ hashes (less than the $2^{69}$ consensual by 2013, but more than the $2^{61}$ of the best claimed theoretical approach, which turned out to have a few rough edges). The phasing out of the first paragraph has become a must. The second and third paragraph of the answer remain valid.


Are there any cryptographic algorithms, which lets the user apply some modifications on the encoded data, without decoding it? I would like to encode some data with a key, and send it to a third party. They don't know the key to decode it, but I would like to make it possible for them to apply some modifications on it. Then they send i back, I can get decode it, and get the result.
For example let the encoded data is the integer 5. I encode it with a key k and it becomes xxxxxx.
The user can apply operations to xxxxxx without knowing k, like +5 and *2. After those operaions, the encoded value becomes yyyyyy.
If I decode the value with the key k, it should be 20, as if I applied +5 and *2 on the original data 5.
Are there any cryptographic algorithms like that?

Can I modify encrypted data without accessing it? if there is an example appreciate it

If access means altering the data without decryption as an attacker then the answer is yes for messages without integrity.

Take OTP, execute bit flipping attack, done.

Take CTR mode, execute bit flipping attack, done.

Take CBC, execute bit flipping attack, done.

Similarly, take any stream cipher, modify one bit,
Let $c_i = m_i \oplus x_i$ where $x_i$ is the $i$th bit form the stream cipher then
$$c_i \oplus 1 = m_i \oplus x_i \oplus 1 = \bar m_i \oplus  x_i$$ where the $\bar m_i$ is the bit complement of the bit $m_i$.

Take CFB, execute bit flipping attack, done

and so on...

These also called the ciphertext malleable.
Note that the reason for this kind of attack is that they are at most CPA secure ( well OTP can have perfect secrecy with fixed-length messages ) and that doesn't mean that the modifications are detectable. To mitigate this attack one needs at least integrity. The integrity may not be enough, since the attack in some cases reuses some part of the encryption and send it. Therefore, at least we need a Message Authentication Code (MAC), like HMAC, GMAC, CMAC, etc. With MACs, the attacker need also forge the message to execute such attacks on the encryption.
Note that the bit flipping is the minimum attack. The attacker can modify more than one bit whenever it fits their aim.

If access means you want to operate on the encrypted data that the answer is yes for a very long time;

Textbook RSA is multiplicative so that you can multiply the ciphertext. Let $(n,e)$ be the public modulus with $d$ is the private exponent. Let the ciphertext $c = m^e \bmod n$ and $c' = 2^e \bmod n$ then
$$c \cdot c' =  m^e \cdot 2^e = (2m)^e \bmod n.$$
One should keep track of the overflow that is when the modifications exceed the modulus the value will be rounded.

ElGamal can be both additive and multiplicative

Paillier encryption is additive where the multiplication of the ciphertext is the addition of the plaintext.

Goldwasser–Micali where the multiplication of the ciphertext is the x-or of the plaintext.

2DNF enables 1 multiplication and many additions.

The above was before Gentry's Seminal work; Fully Homomorphic encryption that enables operation of arbitrary operations on the encrypted data. This was envisioned by On data banks and privacy homomorphisms. by Shamir et. al, immediately after RSA.
The FHE simply having two homomorphic operations on the data so that arbitrary circuits can be computed;
$$E(a) \boxplus E(b) =E(a \oplus b)$$
$$E(a) \boxtimes E(b) =E(a \times b)$$
Note that for the plaintext and ciphertext operations different notation is used since the FHE schemes are not restricted to those. Some notable FHE libraries are;

HeLib, THFE, GSW, BGV, LTV, FHEW,....

There is a post about how these operations handled; Representing a function as FHE circuit


How many RSA keys before a collision? I was wondering how many possible private/public keys exist? If a million people – for whatever reason – would try to generate 5 keys each in the same minute (on the same date and time) is there a high chance of collision? I believe GUID would suffer from that problem as many bits are reversed for date/time (and GUID version) and isn't meant to be used in that way.

Would RSA suffer from collisions if many keys were to be generated in the same moment? Is the amount of possible keys known? I know RSA is based on prime numbers and small numbers are to be rejected. I’m sure values above a certain amount of digits/bits are rejected because software may not be able to support those large values?

So: How many RSA keys before a collision? And if you would try to make many at the same time, would that give you a high chance of collision?

Collisions of RSA keys should never happen for realistic key sizes and good random number generators.

Assume a 1024 bit RSA key; the primes from which it has been derived are about 512 bit. If we assume every 500ths 512 bit number is a prime, and we assume the most significant bit of the 512 bit number is set, we still get about $2^{500}$ or $10^{150}$ different primes. If you apply the birthday problem to these numbers then you would expect RSA keys to have a prime in common about every $2^{250}$ or $10^{75}$ key generations. Identical RSA keys are even more rare.

This is large enough to never happen in practice. Unfortunately bad PRNGs which cause collisions do happen in practice, but you can't translate this into probabilities.

I've neglected a few small factors within the calculations that should not have a significant impact on the outcome.

GUID collisions are a bit more likely. V4 GUIDs are random, except for 6 reserved bits. So there are $2^{122}$ different V4 GUIDs. It's possible to get collisions if you create huge, but achievable amounts of GUIDs if you have a huge system dedicated to creating random GUIDs. The creation of a collision is  very unlikely to happen in a normally sized system, where GUIDs are only a part of the overall security system.

It shouldn't matter in theory that you create many RSA key pairs at the same time, as long as you seed your PRNG with enough entropy. But if you seed badly - so that there isn't much entropy in addition to the system time - then random extraction at the same moment can be a problem. One of the most common randomness related questions in C# is why two instances of System.Random created in quick succession return the same sequence. If the random sequences used for RSA key pair creation are the same, then the RSA key pair will be identical as well.


Multiplexed stream cipher Consider the stream cipher that consists of 3 LFSRs, with the output of one coming being used to determine which of the other 2 is used that clock cycle.

Both the IV and the polynomials are secret.

Is this broken?  I know that the related shrinking generator is not, but needs buffering to avoid timing attacks.

Yes the multiplexing generator due to Jennings, and more advanced versions have been broken. I am assuming regular synchronous clocking of all 3 LFSRs in this answer.

The attacks mentioned are either correlation attacks or linear consistency attacks or a combination of the two. A reference which also cites earlier work is

Optimal correlation attack on the multiplexer generator, Jovan Dj. Golic, Guglielmo Morgari, Information Processing Letters 109 (2009):838–841.


Why is a Feistel Network able to both encrypt and decrypt just by using the round keys in a different order Using a feistel network, to encrypt something you can just use the round keys. But to decrypt it, the same order of processes is applied, however the keys are used in reverse.

My question is: What makes this property of Feistel networks possible?

In short because XOR is its own inverse operation. a XOR b XOR b is a again.

To decrypt an encrypted message we have to reverse the round function. For algorithms like AES (which is no Feistel network but a Substitution-permutation network, in short SPN) we have to reverse most operations like the MixColumn operation. This inversion is called InverseMixColumn. Theoretically we also have to do that for any Feistel network, but they nearly always use XOR as the combination of the one half with the changed other half. The inverse of XOR is again XOR, so we don't have to change it, but can just do the same again.

Take a look at a diagram of Feistel networks. Look at the output of the encryption scheme. Now try to reverse this - go back step by step. You can put one half again into the Round function, get and intermediate result and XOR this with the other half. Now you got back the input before this calculation. Repeat this until you are back at the first input which is your original plaintext. The round keys you used while doing this were the same as for the encryption, but in reversed order.


How does OpenVPN work? I'm confused with the technologies that OpenVPN uses. The official site mentions it uses SSL/TLS in-place of IKEv1/IKEv2, and uses IPSec ESP to secure the data, and yet that it isn't compatible with IPSec.

OpenVPN's security model is based on using SSL/TLS for session authentication and the IPSec ESP protocol for secure tunnel transport over UDP. OpenVPN supports the X509 PKI (public key infrastructure) for session authentication, the TLS protocol for key exchange, the OpenSSL cipher-independent EVP interface for encrypting tunnel data, and the HMAC-SHA1 algorithm for authenticating tunnel data.
Use all of the encryption, authentication, and certification features of the OpenSSL library to protect your private network traffic as it transits the internet
OpenVPN is not compatible with IPSec, IKE, PPTP, or L2TP.

Source: https://openvpn.net/index.php/component/content/article/55.html
Also wikipedia info:

It uses a custom security protocol[9] that utilizes SSL/TLS for key exchange
OpenVPN uses the OpenSSL library to provide encryption of both the data and control channels

Source: https://en.wikipedia.org/wiki/OpenVPN

OpenVPN uses two different protocols. For the standard and most common settings, a TLS link called the control channel is used to exchange a symmetric key. This symmetric key is then used to encrypt a second protocol, the data channel, which uses the OpenVPN protocol itself. The protocol is not identical to IPSec, but it is based off of IPSec ESP, a protocol for secure transport of data over the UDP protocol, which plain TLS cannot do (at the time the protocol was created, DTLS, which is TLS over UDP, did not yet exist). Note that this means that you may be using multiple ciphers for encryption. You may find the control channel using AES to exchange a key that will be used to encrypt the data channel with Blowfish.

Using the control channel with TLS is not the only way to key the data channel. You can also configure OpenVPN to use preshared static keys which will directly be used to derive the symmetric key for data channel encryption. This loses forward secrecy, but gets around the need to use the control channel to exchange a key using TLS.


A RLWE promise problem Let $(R , \chi$)  be a standard RLWE problem instance. I.e. $R$ is a finite degree polynomial ring over a finite field and $\chi$ is some gaussian distribution over R with small variance.

I wonder if the following promise problem is hard.
Let $a_0$ and $a_1$ be two random elements from $R$
The challenger choses a boolean $b$ and two elements $s,e \in \chi$,  and calculates $c= a_b s + e$.

The problem is then:
Given $c, a_0, a_1$, calculate $b$ with non-negible advantage.

For motivation:
If that promise problem turns out to be hard, one could use as natural PQ replacement of PACE, the password authenticated key agreement protocol used in electronic passports. (See
ICAO doc 9303)

(It seems that the proof can be salvaged.)

Let $\text{RLWE}$ denote the standard ring-LWE problem where the secret $s$ is drawn uniformly at random from $R$. Thus, the $\text{RLWE}$ assumption is:
   $$(a,as+e)\approx(a,r):a,r,s\leftarrow R, e\leftarrow\chi,$$
where $\approx$ denotes computational indistinguishability.
$\text{RLWE}$ assumption implies the non-standard LWE assumption [Lemma 2, ACPS09], denoted $\text{RLWE'}$, where the secret is drawn from $\chi$:
  $$(a,as+e)\approx(a,r):a,r\leftarrow R, s,e\leftarrow\chi.$$
The hardness of the promise problem, denoted $\text{RLWE''}$, follows by a hybrid argument (see below) assuming $\text{RLWE'}$ holds. Thus, the chain of reduction is:
 $$\text{RLWE}<\text{RLWE'}<\text{RLWE''}.$$

The hybrid argument. We want to show that the two distributions
  $$D_L:=(a_0,a_1,a_0s+e) \text{ and } D_R:=(a_0,a_1,a_1s+e)$$
are computationally indistinguishable, for $a_0,a_1\leftarrow R$ and $s,e\leftarrow \chi$. Consider the hybrid distribution
  $$D_H:=(a_0,a_1,r)$$
where $a_0,a_1,r\leftarrow R$. We show that $D_L\approx D_H$ and $D_H\approx D_R$, and it follows by transitivity that $D_L\approx D_R$.

To see that $D_L\approx D_H$, suppose for contradiction that it is not: that is there exists an algorithm $\mathsf{A}$ that distinguishes $D_L$ from $D_H$. We show that $\mathsf{A}$ can be used to break $\text{RLWE'}$. The reduction $\mathsf{R}$ is straightforward: given a $\text{RLWE'}$ challenge $(a,b)$ (where $a\leftarrow R$ and $b$ is either $as+e$ or $r$), $\mathsf{R}$ samples $a'\leftarrow R$ and sends $(a,a',b)$ to $\mathsf{A}$ and outputs to its challenger whatever $\mathsf{A}$ outputs. If $b=as+e$ then $\mathsf{A}$ simulates $D_L$; otherwise it simulates $D_H$.

The argument showing $D_H\approx D_R$ is similar.

References.

[ACPS09] Applebaum, Cash, Peikert and Sahai. Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. CRYPTO 2009.


Are there AES-128 keys such that first round key equals last round key? I am looking for AES-128 keys such that the last round key is exactly the first round key (which is simply the key). Any pointer to a proof that they exist or that they don't would be welcome.
In the same line, I am looking for last round keys which are the bitwise inverse of the key or some similarly simple relation with the key.

Not an answer but larger than a comment.
You can ask automated solvers to provide you with keys where the first and last rounds keys match.  Existing solvers likely won't terminate quickly on AES-128 for reasons mentioned in the question and comments.
AES-256, on the other hand, does yield results. For example the keys:

0x623cacba4d7fc6b7914b6bd000a2bcccf0967f268cbafde97ffc5bae4be5d2,
0xfea74943353b4d96d69457a2e6fbe56b1029ca48dc179d1967200df51cee7 and
0xf4e810b7b1c9253e75683304ac4f03f90be6534757600685706d8f6a97bee

all retain the property that expandedKey[0] == expandedKey[nrRounds].


Generating random vector for Full Homomorphic Cryptography The site below explains that part of doing homomorphic encryption, you need to generate a vector of random numbers that have the property that its dot product against a randomly generated bit vector mod 2 has an absolute value less than some amount (but greater than zero).

http://windowsontheory.org/2012/05/02/building-the-swiss-army-knife/

Is there any way to generate such a vector other than brute force?  Seems like it could take a long time for a large vector.

After thinking about it here's what I think.  Let me know what you think.

First, I generate a random vector of floats and figure out what the dot product is.

I then pick one of the elements of the float vector that correspond to a 1 in the binary array (randomly?), and then adjust that value the necessary amount to make the dot product come out to the value I want.

Thoughts? Seems like it should be ok.


Master keys' strengh If I am going to use a master key to generate a session key, why the master key must be "stronger" than the session key?

Like should not be distributing 128-bit AES keys derived from a 56-bit DES key.

The master key has to be stronger in the sense that it's more sensitive than session keys.

The information used to derive session keys are not necessarily secret, so if it's easy to recover the master key, an attacker will be able to compute all the derived keys.

On the other hand, recover a single session key will not help you to recover the master key and so other session keys.

Thus, the effective security strength of the session keys is limited by the effective security strength of the master key.

Say you have:

$$K_{session, i} = \operatorname{KDF}(K_{master}, I)$$

where

$\operatorname{KDF}$ is a one way Key Derivation Function;
$I$ is non-secret key derivation information and
$K_{session, i}$ is a session key derived from a specific $I$.

It's not possible to recalculate $K_{master}$ from $K_{session}$ because the $\operatorname{KDF}$ is one way.

You can however brute force $K_{master}$ together with a known $I$ to derive any $K_{session, i}$.


Weird size of data transmitted in SSLv3 Note - I know SSLv3 is dangerous but that is why I am using it to do demo of POODLE attack using server and client written in python.

So the question is I am using "ECDHE-RSA-AES128-SHA" cipher for connection between client and server.I also implemented the MITM(Man-In-The-Middle) proxy
for connection. And when I am seeing the size of data being transmitted for every message then it is not multiple of 16 bytes.

Data is of like something structure ---

header with 5 bytes -- "\x17\x03\x00\x00 " (yes there is space in the end)
and the remaining encrypted data.Amusingly the new data length by subtracting these 5 bytes is still not multiple of 16.

For single letter messages the size of data transmitted after encryption is 74 bytes(including that 5 byte header which never changes). And as soon as the message becomes more than 11 characters one block of 16 bytes is added so now the size becomes 90 bytes.

Isn't the size supposed to be the multiple of block size? So what is actually the structure of data being transmitted .

Note - I am using ssl.wrap_socket method to create ssl socket

You won't find the answer in the RFC; instead, here's what your SSL implementation is doing: when you send a single byte of data, it actually generates two records.

The first record is empty; so it consists of the 5 byte record header, and the encryption of the 20 byte HMAC tag (which, after encryption padding, is 32 bytes long); this is a total of 37 bytes.

The second record consists of the actual data; so it consists of the 5 byte record header, and the encryption of the data (1 byte) and the 20 byte HMAC tag (which after encryption padding, is 32 bytes long); this is a total of 37 bytes.

This totals to 74 bytes, which is exactly what you're seeing.

Also note that if you send more than 11 characters (and less than 28) of data, then the data along with the 20 byte HMAC data would require 64 bytes; this would extend the total data sent to 90 bytes (again, exactly what you see)

Now, why might an implementation choose to do this?  Well, it's a defense against the BEAST attack.  By including a dummy record up front, it makes the IV used to encrypt the actual data unpredictable (and hence foiling that attack); because the dummy record isn't sent until we actually have the data, the attacker cannot use it's IV value to select the data to encrypt.


Is CECPQ2 forward secure? Is the CECPQ2 key exchange, as deployed by Google[1] and Cloudflare[2] in TLS 1.3 forward secure against quantum computers?

I know that it is using HRSS+SKY as the post-quantum part of the key exchange, but the papers I could find that were describing it do not speak of forward secrecy (either as a present or an absent property).

I do know that the CECPQ2b variant is based on SIKE, and that one has a Diffie-Hellman like operation[3], so it can provide forward secure operation.

I'm mostly interested in how the post-quantum algorithms can provide forward secrecy and at the same time not require use of either HelloRetryRequest handshake in TLS 1.3 or out of band server key distribution.

Forward security (a protocol level feature) and key exchange schemes are indeed two orthogonal topics.

Forward security says the break of a current key does not allow the attacker to learn any communication in the past. To this end, any protocol that uses ephemeral key exchange scheme (i.e., use new keys for new sessions) is forward secure. The only requirement the protocol may have on the key exchange scheme is that the public/secret key pairs can be generated fairly efficiently. (This was not true for RSA, and hence, all the fuss about forward security.) For NTRU-HRSS-SKY this is indeed true. So you will have forward secrecy if you use fresh NTRU keys for every new sessions.


Commitment schemes for arbitrarily large integers My question is about commitment schemes for arbitrarily large integers. One scheme I know uses groups of unknown order (RSA or class group) and depends on the strong-RSA assumption.
You chose a random element $g$ in a group $\mathbb{G}$ of unknown order and define the commitment $Com(n):= g^n$ for any integer $n$. You can turn this into a hiding commitment by choosing an element $h\in \mathbb{G}$ such that the discrete log between $g$, $h$ is unknown and defining the Pedersen commitment $PedCom(n,r):= g^nh^r$ for a randomly chosen secret integer $r$.
Are there other commitment schemes for arbitrarily large integers?
One could decompose the integer and use a polynomial commitment of some sort that does not need hidden order groups, but I suspect such a scheme would not allow for efficient protocols to prove relations between the committed integers.

A small comments: the Damgard-Fujisaki commitment scheme, which you are referring to, does not depend on the strong RSA assumption. If you instantiate it (for example) over RSA group, it is perfectly hiding, and binding under the factorization assumption. However, the soundness of the zero-knowledge protocol for proving relations between integers committed with DJ relies on the strong RSA assumption.
That being said:

In this work, we reduced the assumption for the proofs of relation between DJ-committed integers to RSA instead of strong RSA.
In an upcoming Eurocrypt paper (not yet online, but hopefully very soon), we build a new integer commitment scheme over class groups. The main difference with DJ is that DJ requires a class group with a hard-to-factor discriminant, meaning that you need a trusted setup to generate the parameters. In contrast, we only need class groups with a prime discriminant, which can be publicly generated from a shared random string.
In the same paper, we also build a bounded integer commitment scheme. Unlike the previous ones, the size of the group grows with a bound on the maximum size of the supported integers. However, the scheme still comes with efficient ZK proof systems for proving relations between the committed integers. Furthermore, the commitment and the proofs are secure under the discrete logarithm assumption.
There is always the option of using bit-decomposition of the integer, and committing to the bits, e.g. with a generalized Pedersen commitment (so that the commitment remains compact for arbitrary integers). While this does not directly come with efficient proofs over the integers, for many statements of interest, one can reduce these proofs to statements involving inner products between the committed bits. This was done e.g. in Bulletproof to construct what was (until our upcoming Eurocrypt paper) and still is for some parameters (very large intervals) the most compact range proofs.

As far as I am aware, there does not currently exist any other candidates.


How to generate a good symmetric secret key I would like to generate a good secret key, that later will be used to encrypt data symmetrically.
I am not sure how to generate a good secret key.

I use Linux, I am not sure which sources of enthropy there are.
The idea now is the following:
I can access current timestamp and seed with it PRNG to get some pseudo random value R.
Feed this R into some KDF, for example HKDF and use the result as a symmetric key.
Are there are some loopholes in such scheme?

A "good" secret key should have the same probability as any other possible key to be chosen.

No matter what extractor you will be using, if your entropy source is limited to the current timestamp, this is very unlikely to be the case.

Unless you have access to a hardware random number generator, you should combine as many independent entropy sources as possible.

As to the actual entropy collection, answering your question is impossible without knowing what your environment is.


Is it possible to decide the base of a discrete logarithm? Given $R$, a prime $p$ and two bases $g_1$ and $g_2$, is it possible to decide if $R = g_1^r$ mod $p$ or $R = g_2^r$ mod $p$ without knowing $r$?

It's obviously possible to decide if $R=g_1^r\mod p$ or  $R=g_1^r \mod p$ simply by computing successive powers of $g_1$ and $g_2$ until either $R$ is matched or $g_1$ or $g_2$ respectively is reached. However this is slow.

We can call $g_1$ and $g_2$ "generators" and the set of all values $g^x \mod p$ the "subgroup generated by $g$". You can find $R=g^x$ if and only if $R$ is a member of the subgroup generated by $g$. The number of elements of the subgroup is the "order" of $g$ and a factor of $p-1$

If $g$ is a quadratic residue mod $p$ (i.e it is possible to find an $x$ such that $g=x^2 \mod p$) and $R$ is not a quadratic residue then it's not possible that $R=g^r$. It's possible to determine very quickly (by calculating the legendre symbol) whether a number is a quadratic residue or not for any prime.

This generalises to cubic etc residues for suitable primes.

As Ricky Derner mentions in a comment, the problem is a staple of cryptographic constructions and can be made easy or hard based on the factorization of $p-1$ and the order of $g$.


Does splitting random data reduce its security? Let's say I've got some securely-generated random data I want to encode as words, 32 bits of it.  My wordlist is 2048 words, so each word encodes 11 bits of information.  I write a routine to pack these 32 bits into the lower 11 bits of 3 16-bit types and zero the upper 5 bits of each.  For the last one, I pack in the remaining 10 bits of random data and zero the top 6 instead.  I then look each of these up in my wordlist array to get my words.  I'd like to use these words.

Here's my question: does what I'm doing reduce the amount of secure randomness I'm encoding in these words?  I'd be looking the final word up in a list that's effectively half the size, because the 11th bit is always zero, so is there some "loss of randomness" here?  I know this is a little confusing, but I'd appreciate some guidance.  I suspect there might be some existing guidance on this, but I'm not sure what to search for to find it and none of my googling has yielded results.

Edit: To clarify, my intuitive guess is that this won't pose a problem, but I'm not comfortable going with that.  The closest I've come to rationalizing this is that $2^{11} \times 2^{11} \times 2^{10} = 2^{32}$.

One way to think about this is that you are defining an encoding, and that this is just a change in representation. You are representing a 32-bit value as 3 words, and importantly this is a reversible process. Since it's a bijective mapping, there's as much entropy in the output as there is in the input.

Really, what you're doing is not fundamentally different from representing the 32-bit value in 9 base 10 digits. It's true that there is notable bias in the leading digit, but the important thing is that the full range is covered and it's invertible.


What is the viability of a hybrid vigenere cipher? So a vigenere cipher's main weakness is that you can use frequency analysis on each alternated alphabet, and thus crack the cipher with relative ease... But that implies that you know what the frequency of the plaintext is.

So what if you hybridized vigenere cipher with some other algorithm that obscured the frequency? At first glance, this doesn't seem like a remotely weak system.

You could obscure the frequency using a block-cipher or stream-cipher or use a code-book substitution, then maybe use Vigenere Cipher on it, but if you really want your scheme to be secure, then your underlying substitution must be secure enough. In that case using secure block or steam encryption itself is enough. The second level Vigenere encryption is just a burden, and also a possible backdoor (might lead to lazy people reusing keys, leading to vulnerabilities).

Besides, frequency analysis is its major weakness, but not its only weakness.

Pretending your underlying substitution is weak:

Consider Kasiski examination: If you use a code-book substitution for randomisation (not ideal) or a block-cipher in ECB-mode (which you mustn't) then use a Vigenere key as big as the block, then it is easily vulnerable to this attack. It is still vulnerable if you use a key of a different length. The next step is to break the substitution.

Now consider Key Elimination: Just XOR two consecutive blocks of Vigenere key size, the you get the XOR of the two blocks of plaintext. Now you could break it by finding patterns to guess two possible plaintexts from the first level substitution. It is actually easy if you use something weak.

Pretending your underlying substitution is secure:

If you use a stream cipher, then it is the same as combining the Vigenere key with the pseudorandom keystream, which is not only useless, but could lead to pattern finding as the repetition of the Vigenere key pattern in the PRNG keystream.

Otherwise, just stick to something secure. It would be better, more secure and efficient if you use a stream-cipher with PRNGs like AES-CTR, which is blazing fast and secure.

When could you actually make it secure:

Use the Vigenere Cipher only, but as One-Time-Pad.
Use Vigenere Cipher for a Key Whitening process, where you will have to re-substitute with some block algorithm.


What's the definition of the width of a circuit We consider the size and depth of a circuit under most situations, but recently I read some papers which consider the “width” of a circuit, so I wonder what's the definition of the width of a circuit? I have searched some definitions but they doesn't seem to be well-defined, can you provide a link or a formal definition of the width for a circuit (you can take Yao's garbled circuits as an example)?

The width of a circuit is in some sense related to concept of circuit depth which you appear to already be familiar with. To understand these concepts it is very helpful to think about the graphic representation of circuits in the form of circuit diagrams. I drew an example of such a diagram here:

The depth of a circuit is loosely speaking the number of layers we can partition the circuit into so all gates in layer $i$ can be evaluated if we have the output of all gates in layers $0,\ldots,i-1$. The diagram above is a circuit with three layers, i.e., the circuit has depth three.

On the other hand, the width of the circuit is then the number of gates in the layer with the most gates. So in the example diagram the width is also three because the top layer has three gates.

In the field of secure computation (including Yao circuits) the width of the circuit is typically interesting because it says something about how parallelizable the evaluation of a circuit is. I.e., circuits with wide layers parallelize better.


Modular protocol design What does modular protocol design mean?
Why does TLS not have modular protocol design?

What protocols have modular design? (IPSec, SSH)

By the definition given there, in a modular protocol design,

  each method or scheme used in the protocol (such as the use of nonces
  or the application of a cryptographic schemes) has a clear goal which
  it is proven to achieve, and sub-protocols can be replaced without
  re-proving the security of the remaining protocol steps.

That's also the meaning used there.

The word modular is used with the meaning it has for an engineer: the ideal of building trustable complex systems from smaller trusted and well understood components, in a way such that a component can be replaced with any other having the required, stated properties. That is actually seldom done in real complex systems.

I pass as to if and why TLS, IPSec, SSH... follow, or try to follow, the modular protocol design principle, or not.


Which type of non-basic cipher works better with microcontroller which has no interface and keyboard connected to it? Did a C++ code on Caesar Cipher to do encryption and decryption with my XMC4500 microcontroller but my lecturer said that Caesar Cipher is too simple. He wants me to use a non basic type of cipher and to include size of bit length of plain text and cipher text, secret and public message number and key. And the problem is no keyboard or display interface will be connected to my microcontroller so i could not use printf, scanf, cout and cin to input any of those values. Any ideas on what Cipher I should use and how I could do it?

UPDATE: Thank you for all the suggestions but my supervisor finally told me to use ASCON instead.

That's a 32 bit ARM chip (M4), but without any hardware based crypto capabilities. That means that the best choice of a cipher is one that runs best on 32 bit CPU's, e.g. ChaCha20, SOSEMANUK or NORX (taken from this answer by Thomas). Of course for transport security you may want to use authenticated encryption, but you can always bold that on (this seems to be an assignment after all).

Above ciphers are good ciphers to try to implement yourself. However, if there are ciphers available in libraries then you may want to use those and safe yourself a lot of time. Before implementing a cipher, make sure that this is the purpose of the assignment!

Note that a cipher in itself does not offer security. You need a security design for your system for that.


Proving that a function is negligible My question is about proving that a function is negligible if it is ran polynomial number of times.

This my solution: By the definition of negligibility, we have $negl_1(n) < 1/p'(n)$ where $p'(n)$ is any polynomial. We multiply $p(n)$ both sides: $p(n)*negl_1(n) < p(n)/p'(n)$.

We let $p'(n)>>p(n)$. There is always a $p'(n)$ that satisfies this inequality. Thus, $negl_2(n) = p(n)*negl_1(n)$ is negligible.

Is my solution correct?

Your solution is not correct. You have to show that $\mathbf{\text{negl}_2}$ satisfies the definition of negligible functions and what you "showed" actually is that given any sufficiently large polynomial $p'(n)$, it holds that  $\mathbf{\text{negl}_2} < \frac{p(n)}{p'(n)}$.

I see two easy ways of solving that exercise:

Try to prove it by contradiction supposing that $\mathbf{\text{negl}_2}$ is not negligible and then finding a polynomial whose inverse is asymptotically smaller than $\mathbf{\text{negl}_1}$.
Try to prove it directly: from any given polynomial $p'(n)$, you know that $p(n)p'(n)$ is a polynomial, therefore,  $\mathbf{\text{negl}_1}$ must be smaller than $1 / (p(n)p'(n))$ for all $n$ bigger than some $n_0$...


How is text converted to a number for RSA? According to http://en.wikipedia.org/wiki/RSA_%28algorithm%29#Key_generation the key length is the number of bits in n. So how can a message of many megabytes (millions of bits) be modded by a 1024 bit n? I never hear of a block mode for RSA, for instance.

You never use RSA to encrypt large binary objects, since it's to expensive to do many calculations.

Instead, RSA is used in a key exchange or key transport protocol to send a key for a symmetric-key algorithm, such as AES (with a cipher chaining mode, such as CBC), which is then used to encrypt huge messages.

Also note that textbook RSA isn't secure. Some differences between textbook RSA and deployed RSA are mentioned there: https://crypto.stackexchange.com/a/1449/4874


How are Predicate Encryption algorithms implemented? After a lot of reading on the internet, i can't seem to figure out how Predicate Encryption works.

As i read, it consists of 4 algorithms:

Setup() - (outputs MSK - Master Secret Key and PK - Public Key)

Encrypt(PK, text) - (outputs CT - ciphertext)

GenKey(MSK, predicate) - (outputs a Token)

Query(Token, CT) - 0 if false, 1 if true

I don't understand how the GenKey algorithm works, how u generate a token based on MSK and predicate, and of course, how you query the ciphertext using the generated token.

Can someone point me in the right direction ? Maybe some pseudo-code or very detailed explanation.

Thanks!

At first, your syntax (Setup,GenKey,Encrypt,Query) seems to be the syntax of public-key encryption with keyword-search (PKES). In the case of predicate-based encryption, we use Decrypt rather than Query.

The Sahai-Waters Fuzzy IBE

I recommend Sahai and Waters: Fuzzy identity-based encryption (EUROCRYPT 2005) as a first step. I assume you know the basic of pairing-based cryptography and secret sharing.

In Fuzzy IBE, a ciphertext and secret key is associated with attributes sets, $X$ and $Y$, respectively. If $X$ and $Y$ shares at least $t$ elements, one can decrypt the  ciphertext $c_X$ using $sk_Y$.
The syntax is as follows:

$\mathsf{Setup}(1^{\kappa},n,t)$ outputs $msk$ and $pk$, where $\kappa$ is the security parameter, $n$ is the size of universe, and $t$ is a threshold parameter.
$\mathsf{GenKey}(msk,Y)$ outputs $sk_Y$, where $Y \subseteq \{1,\dots,n\}$.
$\mathsf{Encrypt}(pk,X,m)$ outputs a ciphertxt $c_X$, where $X \subseteq \{1,\dots,n\}$.
$\mathsf{Dec}(sk_Y,c_X)$ outputs $m$ if $X$ and $Y$ share at least $t$ elements.

They design the scheme as follows (I omit enc and dec):

Setup: the master secret key is $\alpha,t_1,\dots,t_n \in \mathbb{Z}_q$ and the master public key is $e(g,g)^{\alpha}$ and $T_i = g^{t_i}$.
GenKey: The master generates shares $s_1,\dots,s_n$ of $\alpha$ by using $(n,t)$ secret sharing scheme, computes $D_i = g^{s_i/t_i}$ for each $i$, and returns $D_i$ for $i \in Y$.

Other schemes

Predicate-based encryption schemes based on the paring groups often employ this structure. Intuitively speaking, they hide/share the master secret into user secret keys as Sahai and Waters did.

If you need examples of implementations, we can find (proof-of-concept) implementations of more complex predicate-based encryption schemes in cryptographic libraries:

PBC and jPBC
Charm


How secure is a 4 digit seed? When I Use a 4 digit random number(e.g. 4468) as seed for a (manual) Stream cipher and straddle it to the length of the plaintext using a lagged fibonnacci generator, can  this seed be found by brute force?

Assuming by "digit" you mean "base-10 number"...

There are $10^4$ different combinations.

$\log_2(10^4) \approx 13$

It would require no more than $2^{13}$ guesses to guess every single possible seed. This assumes that the seed is uniformly random.

Even using python on relatively modest hardware, it takes .001 seconds to iterate over all the possible seeds.

So yes, it is easily guessable.

You would require at least $2^{64}$ cost to become merely inconvenient rather than trivially guessed.

The minimum size for it to be considered secure is 128 bits. That would correspond to roughly 39 uniformly random base-10 digits.