How to compare the order of elements in cyclic groups? In a cyclic group with randomly looking behavior like the one used in secp256k1, is there any known efficient algorithm to compare the order of two randomly given elements $P_1$ and $P_2$ and find out which one will appear first starting from a known generator point of the cycle? If such algorithm exists, would that be considered a weakness?!

Consider that we have two known integers $a$ and $b$ so that $a>b$. Taking $P_1=a\times G$ and $P_2=b\times G$ we can say $P_2$ has a greater order in the cycle, meaning that starting from the generator point it will appear before than $P_1$.

By this definition is there any known algorithm based which one can compare the order of two random elements of the group $P_1$ and $P_2$?

By this definition is there any known algorithm based which one can
  compare the order of two random elements of the group $P_1$ and $P_2$?

No, such an algorithm would allow for an easy break of the elliptic curve discrete logarithm problem. But as this problem is assumed hard for secure curves like secp256k1 us knowing such an algorithm is impossible.

To see this fix the reference generator $G$ to the standard one for the curve with the generator having order $q$. Furthermore let $P=xG$ be the challenge point for which we want to recover $x$. Now define $a=1$ and $b=q-1$.

Compute $m=\frac{a+b}{2}$ and $M=mG$.
Check whether $M=P$ and if so, return $m$.
Check whether $M<P$ using the conjectured algorithm. If this is true, set $a\gets m$, otherwise set $b\gets m$.
Go to 1.

This is a standard binary search as you may have recognized and it will find the discrete logarithm in about $\log_2 q$ scalar point multiplications and algorithm evaluations which is quite efficient.


From the product of two permutation matrices raised to the same power, is it easy to find the power? Let $A$ and $B$ be two public permutation matrices.
If $r$ is a secret power of large number, can we easily find $r$ from $A^rB^r$?

The product of two permutation matrices is itself a permutation matrix. So there's nothing special about its "factors" being public.  You should consider a single public permutation matrix $A$ and finding $r$ from $A^r$.

  Edit: oops, this was based on a misinterpretation of the question.

And there's nothing particularly special about it being a matrix. If $A$ is a permutation matrix corresponding to permutation $\pi$, then $A^r$ is the permutation matrix corresponding to $\pi$ composed with itself $r$ times. Let's call this permutation $\pi^{(r)}$.

So the question boils down to to the "discrete log" problem in a permutation group: given $\pi$ and $\pi^{(r)}$, find $r$. This problem is easy.

First, observe that if $\pi$ is a simple cycle on $n$ items then $\pi^{(r)} = \pi^{(r \bmod n)}$. Since $n$ must be small in this problem, you can easily just "brute force" to determine $r$ mod $n$.
Second, any permutation can be uniquely decomposed into disjoint cycles. The operation $\pi^{(r)}$ acts independently on all the cycles of $\pi$. So if $\pi$ is composed of cycles of length $k_1, k_2, \ldots$ then we can use the above trick on each cycle and learn $r \bmod k_1, r \bmod k_2$ and so on. Then you can use the CRT to solve for $r \bmod \textrm{lcm}(k_1,k_2,\ldots)$. And indeed, the order of $\pi$ will also be $L=\textrm{lcm}(k_1,k_2,\ldots)$ in the sense that $\pi^{(L)}$ is the identity permutation.

So you can efficiently identify $r$ as uniquely as is possible (mod $L$).


Protocol for proof of knowledge of $l$-th root Assume we have Group G in which the adaptive root assumption holds.
This assumption states that if we choose an element $w$ and after that, if we receive a prime value $l$ it is hard to find the $u$ such that: $u^l = w$

Now suppose I want to prove that I know a $l\text{-}th$ root of an element $w$ without revealing it. (I don't want to reveal $u$). Is there any protocol for this?

The immediately obvious solution would be this simple cut-and-choose protocol:

Prover: selects a random value $v$ and sends the value $y = v^\ell$
Verifier: selects and sends a random bit $b$
Prover: if $b=0$, sends the value $t_0=v$.  If $b=1$, sends the value $t_1=vu$
Verifier: if $b=0$, then verify that $t_0^\ell = y$.  If $b=1$, then verify that $t_1^\ell = y w$

The standard zero knowledge logic works - if the prover knows a $y$ value for which he knows both correct responses $t_0$ and $t_1$, then (assuming that inverses are also easy to compute) he can recover the value $u$ (hence, if he succeeds with this protocol a number of times, then the probability of success without him knowing $u$ is minimal).  And, only one of the answers does not give any information to the verifier.


RSA - Very big Modulus and Ciphertext Is there a known weakness in RSA when the value of modulus (n) is very large?

n = 2466 digits
e = 65537
c = 2466 digits

n cannot be factorized. I checked on factordb.com and no factors were present.

Both, modulus and ciphertext have the same number of digits. Is this not considered secure?

What kind of attacks can be used against such a crypto system?

2466 digits for an RSA modulus is somewhat large, but not unseen. A larger RSA modulus, when it is properly sampled, can only lead to a better security guarantee. The ciphertext in RSA is $c = M^e \bmod n$, where $M$ is something derived from the input message $m$ - hence, it is perfectly normakl for $c$ to have the same bit length as $n$ (anything significantly smaller would be a weakness, anything significantly larger... would not be a valid ciphertext). This choice of $e$ is also the most common one. Hence, there is nothing wrong with your proposed choice of parameters, provided that $n$ was indeed generated as the product of two random length-$1233$ strong primes.

  n cannot be factorized. I checked on factordb.com and no factors were present.

Note, however, that this gives you essentially zero indication about the actual security of this modulus. It is only a secure modulus if it was generated as a product of two equal-length random strong primes, with a good random number generator. $n$ could be a very weak RSA modulus if it was not generated this way, yet you would not immediately find the factors with an online tool.


Most secure 32-bit block cipher I have very short messages which I want to keep to 32-bits encrypted (ie one block). The keys can (and should) be as large as possible to maximize security.

However, I don't know many ciphers with 32-bit modes. Are there any that offer 90+ bit security? Which has the most cryptanalysis?

If you care about security, and don't care much about performance, you might consider a Format Preserving Encryption mode such as FF1; this is a mode of operation that uses a 128-bit block cipher to form an arbitrary sized block cipher; this arbitrary size includes a size of 32 bits.

It is believed (I don't think we have a proof in hand) that, if instantiated with AES, it is as strong as AES (with the caveat inherent with having a block size of 32 bits); hence you have at least 128 bits of security.

Performance isn't great (performing an encryption or decryption of a single block involves 10 AES operations), however depending on what your use case is, it may be quite acceptable.


RSA message integrity I wish to send some small data that RSA alone can encrypt, and I send a shared secret along with it.

A --> B ; RSA(data||shared_secret)  // B will verify the shared_secred and authenticate A;

vs

A --> B ; RSA(data||shared_secret) || SHA-256(data||shared_secret)

RSA is RSA-OEAP, not something home grown.

Will verifying the shared secret be enough for message integrity and authenticity? Or, should I also send a hash of the message?
I wish to ask because it seems redundant to send twice as much data if I do not need the hash.

If shared_secret is a plain text password as we are told, then the second method, which sends
   RSA-OAEP(data||shared_secret) || SHA-256(data||shared_secret)
is unsafe.

That's because a guess of data allows to mount an off-line check of the password by comparison to the known SHA-256(data||shared_secret). That's ideal for password cracking. That also applies if we change SHA-256(data) to HMAC-SHA-256(shared_secret, data), which is a way of constructing a MAC from a hash with a security proof/argument.

For the same reason, that construction also compromises the confidentiality of data.

It remains to determine if A sending
   RSA-OAEP(data||shared_secret)
to B (computed with B's public key), and having B decipher (with B's private key) and verify shared_secret, is enough for insuring integrity and authenticity of data; assuming of course, that no adversary could have learned shared_secret.

My answer is: no, that does not give the desired insurance of integrity and authenticity, at least for some possible ways of establishing or using shared_secret. In particular:

If there was any prior use of shared_secret by any party knowing it, that involved sending
  RSA-OAEP(something||shared_secret)
per B's public key, then poof goes the desired integrity and authenticity of data, because an adversary can reuse that cryptogram to abuse B into believing that data is that unrelated something.
That includes if shared_secret is merely used for several iterations of the protocol involving different values of data.
Independently, it is quite possible that the check B makes of that message can be used as an oracle to test shared_secret; if that is a password (as we are told), this is bad (though not nearly as bad as with the other protocol, because that's an online attack). Then, after shared_secret leaked, the sky is the limit.

On the other hand, if shared_secret was a wide secret of fixed length established by XOR of secrets chosen by authenticated parties, and RSA-OAEP(data||shared_secret) was the only time shared_secret is used other than as the key of a symmetric algorithm, then I see no reason why the objective would not be met. This is no insurance.


Easy hash function collision I'm designing a cryptography-breaking assignment for a college-level introductory security course, and I'm looking for a hash function which is reasonably easy (but not too easy) to generate collisions for. The assignment is that the students are given a hash table implementation which uses such a function, and their task is to design a series of inputs which will tank the hash table's performance. I was originally thinking of modelling it off of PHP's associative array attack from a few years ago, but it's actually too simple (for integer keys, the index used is literally just the integer modded by the table size). Any ideas for something that might be a tad harder than this, but not so hard that a bunch of sophomores with a week's worth of crypto lectures couldn't solve it in a reasonable amount of time?

Thanks!

EDIT: To clarify, I'm looking for hash functions which are not cryptographically secure, and can be easily inverted (or at the very least caused to collide) without brute-force search of the input space. As a general rule, hash functions which you could even mistake for cryptographically secure are probably too hard to break for this assignment.

A mathematically elegant and rather simple way of hashing are the parity bits of a Hamming code, as small changes in the data will yield different parity bits. You can weakly hash 4-bit strings to 3-bit strings with the standard (7,4) Hamming code, but the general Hamming code construction has high enough rate that you can hash longer strings (say, 26 bits to 5 bits) with a very simple algorithm and give them a hint by showing how to break the (7,4) hash.

Actually, it does sound like a fun homework assignment to find a string of length $2^{20} - 21$ that hashes to a particular $20$ bit string using a $(2^{20}-1, 2^{20}-21)$ Hamming code

Of course there are better "real hashes", but you didn't want that, right? :)


Achieving 32-bit verification code with 16-bit CRC? I am programming an embedded chip that has a hardware 16-bit CRC module. I have to protect some data bytes $d_0,d_1,...,d_{n-1}$ against corruption caused by sudden loss of power; a 32-bit CRC would provide the level of protection that I need, but the chip doesn't have that capability.

Unfortunately the CRC module uses a hard-coded polynomial that can't be changed. And I need the computation to be as fast as possible. Perhaps a table-based CRC algorithm would be fast enough, but the table would occupy 1 kilobyte of ROM, which I want to avoid if I can.

So my question is this: Can I somehow use this hardware CRC-16 module to reach the level of security that I need?

My current idea is to compute $CRC_{\mathrm{forward}}$, the CRC-16 of the data bytes $d_0,d_1,...,d_{n-1}$, and $CRC_{\mathrm{backward}}$, the CRC-16 of the data bytes $d_{n-1},d_{n-2},...,d_0$, and simply concatenate these two 16-bit CRCs to create a 32-bit EDC. Is this sufficient? Or are these two CRCs in some sense dependent?

More precisely: Suppose $D$ is the data, and $E$ is a corrupted version with $E \ne D$. Then I want the probability that $CRC_{\mathrm{forward}}(E) = CRC_{\mathrm{forward}}(D)$ to be independent of the probability that $CRC_{\mathrm{backward}}(E) = CRC_{\mathrm{backward}}(D)$. Is this the case here, or have I missed something?

Edited to add: If the discrepancy $E \oplus D$ is palindromic, and $CRC_{\mathrm{forward}}(E) = CRC_{\mathrm{forward}}(D)$, then $CRC_{\mathrm{backward}}(E) = CRC_{\mathrm{backward}}(D)$. So this idea doesn't work. Does anybody have a better idea?

I'll assume $n$ is a multiple of 4. One option is to compute the CRC16 of the bytes $d_{4j},d_{4j+1}$ ($0\le j<n/4$), giving 2 bytes appended as $d_{n},d_{n+1}$; and the CRC16 of the bytes $d_{4j+2},d_{4j+3}$, giving 2 bytes appended as $d_{n+2},d_{n+3}$.

That

reduces the work compared to the original solution, because each byte is processed once instead of twice;
has a desirable property of CRC32: if all bits in error are within the same 32-bit segment of data+CRC (including within the same 32-bit word), then the error is detected [note: the capability to always detect short error bursts lying across data and CRC requires care in the finalization of the CRC];
detects a large number of random errors with odds comparable to a 32-bit CRC, including all errors affecting an odd number of bits.

One very negative aspect compared to a 32-bit CRC is that errors which, for hardware reasons, are bound to always affect the same single bit of a 32-bit word (or some wider multiple) are not detected far more often ($2^{-16}$) than for a 32-bit CRC ($2^{-32}$).

Therefore, that solution is fine to detect communication errors on a serial link, but poor to detect corruption of a Flash or DRAM memory (assuming there is no built-in ECC) as occurring from a defective sense amplifier, and I guess a marginal write.

In the context of detecting corruption in memory (without ECC), I would consider

computing a CRC16 of the whole data;
simultaneously counting the number of 0 bits in the data (which will fit 16 bits if $n<2^{13}$);
storing the concatenation of that along the data.

Integrity check using the count of 0 bits has the property (desirable in the context of storage in computer memory without ECC) that if an error changes all bits in error to the same value, then it is always detected (that includes errors in the count). Also, it is fast to compute even on CPUs without hardware popcount, using a small table or various bit tricks.


Padding RSA with random number I known the post from here and here regarding RSA padding. I still don't understand why simple addition of the message with an random number and then encrypting the result with plain RSA isn't secure.

Here's a more precise description of the scheme:

Suppose the message is $m$. Then suppose we draw a random integer $r$ and compute $m'=m+r\bmod n$ and feed $m'$ to the RSA function.

At a later time I will recover the encrypted message from the server and I'll decrypt it myself. I known that RSA isn't best scheme for this application. Is the proposed padding secure in this context?

The system proposed has no practical interest.

If $r$ is public, then it is easy to check a guess $\overline m$ of $m$ (compute $\overline m'=\overline m+r$, feed it to the RSA function, and compare the result to the actual ciphertext; it matches when $m=\overline m$). That possibility is a disaster in practice; e.g. if $m$ is a name on the class roll, or a credit card number, poof goes confidentiality.
If $r$ is secret and chosen randomly in $[0,n)$ for each message, then the system is safe and we can use $m'$ as the ciphertext, without needing RSA on top of that. That's in effect a One Time Pad.


Brute force strategy I am a beginner in this field, and I was thinking about brute force strategies to break symmetric key encryption.
Let's say we have a block cipher in CTR mode and the key is 56 bits in size. What would a process of finding the key look like (brute forced strategy)?

Brute forcing the key simply means iterating over all the possible keys, assuming you know the mode of operation (in this case CTR) and the IV. Then if a likely plaintext is found then you've found your key.
It's always possible you find the wrong key, but the chances of you doing so diminishes with the amount of bits known of the plaintext. Usually you know enough about the plaintext to do so.
For instance, you can use the fact that the highest order bit of ASCII is always zero, most files have specific headers, you can do frequency analysis, etc. etc. If you perform an attack you might as well assume you know, say, 4 blocks of plaintext. In that case you can be next to certain that you found the right key to decrypt the rest.
Note that brute force attacks are very easy to parallelize; just split the key space and perform the decrypt / validation phase in separate threads.


libsodium vs gnupg curve25519 compatibility I am trying to create deterministic GPG keys based on cryptosteel. I have implemented a library for (de)serializing PGP packets and am now trying to use keys generated in libsodium for import in GPG.

Libsodium gives me a 32-byte public key and a 32-byte secret key. This is also what PGP seems to use - except PGP prefixes 0x40 to the public key to indicate it isn't using point compression (and thus becomes 33 bytes).

ed25519 keys work fine, but curve25519 keys don't work, when trying to import the generated key GPG asks for a passphrase - despite not specifying a KDF. It seems the points generated by libsodium are not compatible with GPG.

A few random things I don't understand, that may be related to this:
- GPG points are 32 bytes, but they are uncompressed. Shouldn't they be 32 + 32 bytes then? From all I can read it seems both X and Y should be 32 bytes.
- Libsodium might be using compressed points, but their points don't start with 02 or 03 - which I read is used to indicate which Y was taken for the key. They are also 32 bytes, which would also be too small if you consider an extra byte to indicate the compression.

Does anybody know what exactly is different between these curves and what I could do to fix it?

Found the solution. All that was needed was to reverse the bytes in the curve25519 secret point. Apparantly PGP uses little-endian for this, while ed25519 uses big-endian.


Camellia cipher - is it a symmetric or asymmetric cipher? I read a wiki page about Camellia cipher and know that it is a block cipher that can use 128-bit, 192-bit or 256-bit keys. But I cant find any information about if its a symmetric cipher (uses one key for both encryption and decryption) or asymmetric cipher (uses different key for encryption and different key for decryption)?

And in which cipher modes can Camellia operate? (ECB,CBC, ...)?

Camellia is a symmetric block cipher; the same key is used for both encryption and decryption.  And, as a block cipher, it can be used in any of the standard modes (CBC, CTR, CFB, GCM, even ECB, although use of ECB for any block cipher is not encouraged).


Paillier: guessing the message when knowing the cipher and the random number I cannot get my head around this.

In Paillier, the ciphertext is calculated using

$c = g^m.r^n\ mod\ n^2$

where $(n,g)$ forms the public key and $r$ is a random number $0<r<n$.

Assuming an attacker knows $c$, $r$, $n$. and $g$, what would it take  - in average - to find $m$ ?

You don't need to guess, you can find $m$ for sure.

If you know $c,r,n,g$, then you can eliminate $r^n$ from the ciphertext and get $c'=g^m \bmod n^2$.

In $Z_{n^2}^*$, we have $(n+1)^x = 1+nx \bmod n^2$ ($x\in Z_n$). Therefore:

If $g=n+1$ is used, then $c'=g^m \bmod n^2 =1+mn$, then you can find $m=(c'-1)/n$.
If $g\ne n+1$, since the order of $g$ must be a multiple of $n$, we have $g= (1+n)^a=1+an \bmod n^2$ for some $a$, then we can find $a=(g-1)/n$. Then $c'=g^m \bmod n^2 =1+amn$, and we can compute $m=(c'-1)/an$.

Added based on Bruno's comment: the general forumula (for all $g$) is $m=(c'-1)/(g-1)$.


Paillier scheme and noise growth Does the problem of noise growth exist in the Paillier homomorphic scheme ?

Does the problem of noise growth exist in the Paillier homomorphic scheme ?

No, it does not.  Unlike Lattice-based schemes, you can do as many homomorphic additions as you want in Paillier (without doing anything like a "reboot"), and it's never a problem.


Is a padding oracle attack possible if data is only encrypted internally on a server (e.g. for storage)? I read something about the padding oracle attack when analysing the use of an AES-encryption of data in a database and was "scared" it could be a serious issue.
But after investigating a bit further, I now came to the conclusion that in our specific scenario it should be no matter at all. I would like to validate this, because I have the feeling to not fully understand the attack method.

I have got the following scenario:

Clients send plain text messages to an application server (Java). This messages shall be stored in a database, but not as plain text; they have to be encrypted (synchronous encryption with a static encryption key). We use AES-128/CBC/PKCS5Padding, while the encryption is done by the application server, which is the only instance that knows the encryption key.
This means, the server does not offer an external interface, which could be used to send (modified) encrypted data packages. So there should be no chance for an end user / external hacker to do an padding oracle attack.
Or, in other words, there is no instance / server acting as "oracle".

The only attack scenario would be an internal attempt to hack the encryption, let's say a person who has access to the database (e.g. a database administrator with a criminal attitude) and by that to the encrypted messages. But due to the fact the application server does not offer any interface and the attacker does not have access to the encryption key, he should have no opportunity to make an padding oracle attack (?).

Also, an attacker would not discover the encryption key by being successful with an padding oracle attack, he only would decrypt specific messages. So even if the database administrator with access to the database and with an account for the application would change the encrypted data directly in the database to check if decryption still works (the data is displayed in the client / web site = no padding exception), he only could decrypt his own data by doing that, which actually wouldn't be of any use for him.

My question: Do I understand this right or do I miss anything important?

As far as I can tell, you just have encrypted data in a DB and are worrying that it can be hacked. In short, encryption works so you're good.

In more detail, your analysis of a padding oracle attack is correct. As you don't have any services or APIs or network protocols that partake in the encryption, a padding oracle attack can't occur.

Understanding that I don't fully understand your architecture, I can tell you about the attacks I'd worry about:

There are potential client-side attacks. Perhaps via OS or browser malware. Not your app's fault but can still lead to an exposure of your data.
If you have a malicious admin, they could attack your application directly. They could potentially modify your class files to extract your data while it's in motion. Worse, they can call your decryption functions to bulk decrypt the DB.
Examination of your app's memory to look for secure data or the encryption key.
Examination of your app's configuration to get your decryption key.
An application vulnerability that allows a remote attacker to extract data from your app or cause it to perform malicious actions. This may be the biggest threat as it allows for remote attacks.

I'm sure there's more but that's my quick evaluation. I think that the breaking the DB encryption is far down the list of things to worry about. Secure your key (preferably in a password-sealed keystore) and secure your app against a remote attack.


Two possible plaintext's using OTP decryption I am using this cipher-text

c   = 04 10 12 00 01 08 67 0A 19 65 0F 03 0A 00

with two possible keys

k_1 = 45 44 46 41 42 43 47 4B 4D 45 4B 42 5D 4E

and

k_2 = 45 44 46 41 42 43 47 4B 4D 45 41 4C 45 4E

If I decrypt the cipher-text with k_1 I am getting 'ATTACK AT DAWN' and with k_2 'ATTACK AT NOON'. Which of the plaintexts is more likely to be the original plaintext and why?

Which of the plaintexts is more likely to be the original plaintext and why?

A very literal and devious answer to the question (at least as you have posed it) is that 'ATTACK AT DAWN' is more likely to be the original plaintext because it can be independently established that attacks at dawn are more common than attacks at noon.

Which means there's a subtle flaw in the question: what cryptanalysis is supposed to accomplish is to use the ciphertext as evidence that favors some candidate plaintexts over others. The point isn't really which plaintext is more likely, it's whether an analysis of the ciphertext can rationally demand that you change your mind about their relative likelihood. Like, you go into it thinking that 'ATTACK AT DAWN' is twice as likely as 'ATTACK AT NOON', but analysis of the ciphertext compels you to conclude some other proportion.

The point of all this is the often-missed nuance that the famous perfect secrecy of one-time pads is not that the attacker cannot figure out what candidate plaintext is more likely, but rather that analyzing the ciphertext is of no use in achieving that end.


How can I prove that a set of ciphers are the encryption of a set of plaintexts? I have a set of plaintexts e.g., ["how", "are", "you"] and a sender who encrypts each element with a unique symmetrical key (or not) and outputs the set of ciphers.

Receiver needs assurance that all the ciphers he just received have a one-to-one mapping with the ["how", "are", "you"] and not some other values. I'm not using asymmetric encryption because it'd reveal which cipher represents which item.

I have read all other questions and a few papers on set membership, pederson commits, etc but still can't understand how it'd work. It'd be very helpful if you could give a detailed answer.

If you are allowing for probabilistic proofs, simply have the one doing the encryption encrypt the set multiple times. All of these encrypted sets are sent to you.

You then ask the one doing the encryption to reveal the keys for all but one of the sets. You do the decryption to verify that all of those sets decrypt to the proper plaintexts. This is a cut-and-choose protocol (see Cut-and-Choose Protocol by Crépeau).

If the adversary is going to cheat, they will only be able to encrypt one set incorrectly and you have to randomly not choose that set for verification. You can set the probability of this to be arbitrarily low (at the cost of communication and computation) by setting the number of copies of the set the one doing the encryption must encrypt to be high enough.


Blowfish ECB mode: Tools for known-plaintext attack? I'm currently dealing with multiple blowfish-encrypted files that share the same key. All are encrypted using ECB mode judging from their appearance:

I don't know what the key is but I know 64 byte (or 6 blocks) of consecutive plaintext. The key length used is most certainly 448 bit.

Now, I just recently started to read up on this topic and I haven't been involved into cryptography before either. However I stumbled across this post on this site and it talks about precomputed tables to bruteforce the used key. I understand that the post is talking about a 40bit key so it eventually means that there is no way to use this in my situation.

But if it is, are there any tools to use for this scenario? I'm sadly lacking the skills to write them. I just want to be able to decrypt and re-encrypt the files.

Thank you very much for any reply.

No, the most you can do is to compare ciphertext blocks for equality and link those blocks with identical plaintext. That ECB is used does not hurt the security of Blowfish by itself. Block ciphers should not be vulnerable to known plaintext attacks, and there seems to be no known attack on Blowfish in this regard.

To state it a bit more formally: that ECB is used or that plaintext is known does not make the cipher itself distinguishable from a random permutation; the repetition of ciphertext blocks only show that it likely is a permutation.

Obviously, brute forcing such a large key is out of the question. That there are attacks on 40 bit keys doesn't translate to keys over 64 bits let alone keys of more than 11 times the size.


Difference between Key Scheduling and Key Generation? I am a little bit confused in the terms i.e Key Scheduling and Key Generation. What is the actual difference between these two terms? According to Wikipedia, the terms are described as:

Key Generation: Key generation is the process of generating keys in cryptography. A key is used to encrypt and decrypt whatever data is being encrypted/decrypted. A device or program used to generate keys is called a key generator or keygen.

Key Scheduling:  A key schedule is an algorithm that calculates all the round keys from the key.

From the above definition and after reading more details about this on the internet what I summarized is:

Key generation is just a process while key scheduling is about the calculation of key in the algorithm. Means this process is called key generation, am I right here?

Moreover, what we will be called if we calculate a key using any method in our algorithm. Just for example say that I calculate a key using different chaotic equations. Combine these equations in a particular way and generate a final key. Is it will be key scheduling or key generation?

Key generation is just a process

Anything is "just a process", executing any algorithm is "just a process". So lets ignore this part of the sentence as it doesn't make sense.

  while key scheduling is about the calculation of key in the algorithm.

That's right. If the algorithm requires a key in a different form, e.g. expanded from the original form, then the key schedule is the part of the algorithm that performs that calculation.

However, this argument is true when we're talking in the context of a block cipher. Key schedule could mean other things in other contexts.

  So now the sentence reads "Means (the process or procedure that is taking place in generating a key) is called key generation, am I right here?".

That sentence is self-evident. However, as long as "generation" is not further clarified, it carries no weight.

  Moreover, what we will be called if we calculate a key using any method in our algorithm

That depends if we're still talking in the context of a block cipher I  suppose. If you're deterministically transforming your key within your algorithm then I suppose you can call it a key schedule. You can also call it something else; it is your algorithm after all.

  Just for example say that I calculate a key using different chaotic equations. Combine these equations in a particular way and generate a final key.

If you do that deterministically and within your algorithm then nobody would raise an eyebrow if you call it a key schedule. It would help if your algorithm would be a block cipher.

They would raise an eyebrow if you try and use it to increase the key strength or if the method takes lots of time, because that is not what key schedules are generally about.

  Is it will be key scheduling or key generation?

Key generation supposes randomness, and randomness supposes some source of entropy. If no source of randomness is given then we can confidentially say that it is not key generation.

If it is a key schedule is already discussed above. There are other options such as key establishment. However, if there is a single key as input, and if the supposed key schedule is happening within your algorithm, then it makes sense to call it a key schedule.


How many qubits are required to break RSA 2048 or 4096 with a universal quantum computer? So in the news this week, IBM have created a universal quantum computer with 5 fully functional qubits. Logic and Moore's law dictates they will be able to scale this up to a lot more qubits within a few years. With Shor's algorithm, elliptic curve cryptography will likely be the first to fall as it has lower key lengths and therefore a lower number of qubits are required to break it. If using RSA with larger key sizes e.g. 2048 bits, this may buy a few more years of time, hopefully then a transition to post-quantum algorithms can be made.

Does anybody know:

How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer?
How many qubits are required to break Curve25519?
I want to work out the relationship between the key length and number of qubits required to break that key length. Is there a simple layman's formula for working out how many qubits are required using the number of key bits and number of qubits as inputs into the function? E.g. n = number of public key bits, q = number of qubits the machine has, a = the answer (number of qubits required to break it). Maybe the formula is just a = n = q, i.e. 2048 qubits are required to break RSA 2048.

If you can prove your answer with citations to any papers or research that would also be beneficial.

Edit: I have found this answer. Anyway if I plug in N = 2048 to the Θ(log(N^2)) equation, this gives me 15.25 qubits required to factor RSA 2048. RSA 4096 bits is not much better, requiring only 16 qubits. Is that correct?! Why is everyone not running around with their hair on fire?

How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer?

Like the answer you linked to shows, about $\log_2(N^2) = 2 \log_2(N)$ or just $2n$ where $n$ is the number of bits of the modulus $N$, i.e. the key size of RSA. So 4096 for 2048-bit RSA, double that for 4096-bit.

This paper (PDF) has an algorithm using $2n+3$ qubits, where $n=\log_2 (N)$, where $\log_2(N)$ is the way to calculate the number of bits in $N$.

  How many qubits are required to break Curve25519?

Breaking elliptic curves requires (pdf, see 6.2) roughly $6n$ qubits where $n$ is the order or key size of the curve, which for Curve25519 would be $6 * 255 = 1530$. Less than secure RSA sizes require, but much more than has been accomplished.

  I want to work out the relationship between the key length and number of qubits required to break that key length.

See above.

  Edit: I have found this answer. Anyway if I plug in N = 2048 to the Θ(log(N^2)) equation, this gives me 15.25 qubits required to factor RSA 2048. RSA 4096 bits is not much better, requiring only 16 qubits. Is that correct?! Why is everyone not running around with their hair on fire?

You are using the wrong value for $N$. It is the modulus, not the bit length. The actual number of qubits needed for 2048-bit RSA is about 4096.

Note (from removed comment to the present answer):  We're talking about ideal qubits here. Error correction might increase the number of physical qubits beyond these numbers.


Find hash and signature algorithms used in an X.509 certificate signed with RSASSA-PSS I'm trying to understand the new PSS scheme, but having trouble figuring out how to parse it properly.

When receiving a certificate with OID of RSASSA-PSS, how can I know which hash and signing algorithm was used?

The ASN.1 module

The OID of RSASSA-PSS is specified as below, however, it should only be used as part of an AlgorithmIdentifier, which is a SEQUENCE of the OID, followed by the parameters. These parameters are NULL for PKCS#1 v1.5 signatures, but for PSS they must be present

Here is the OID:

   --
   -- When id-RSASSA-PSS is used in an AlgorithmIdentifier, the
   -- parameters MUST be present and MUST be RSASSA-PSS-params.
   --
   id-RSASSA-PSS    OBJECT IDENTIFIER ::= { pkcs-1 10 }

and here are the configuration parameters of the algorithm:

   -- AlgorithmIdentifier.parameters for id-RSASSA-PSS.
   -- Note that the tags in this Sequence are explicit.
   --
   RSASSA-PSS-params ::= SEQUENCE {
       hashAlgorithm      [0] HashAlgorithm      DEFAULT sha1,
       maskGenAlgorithm   [1] MaskGenAlgorithm   DEFAULT mgf1SHA1,
       saltLength         [2] INTEGER            DEFAULT 20,
       trailerField       [3] TrailerField       DEFAULT trailerFieldBC
   }

where the hashAlgorithm defines the hash over the data, just like for PKCS#1 v1.5 signatures specify a hash over the data within the message.

However, we still have an undefined maskGenAlgorithm of the type with the same name:

   MaskGenAlgorithm ::= AlgorithmIdentifier { {PKCS1MGFAlgorithms} }

... that's not very helpful, so lets dive deeper:

   --
   -- Allowed mask generation function algorithms.
   -- If the identifier is id-mgf1, the parameters are a HashAlgorithm.
   --
   PKCS1MGFAlgorithms    ALGORITHM-IDENTIFIER ::= {
       { OID id-mgf1 PARAMETERS HashAlgorithm },
       ...  -- Allows for future expansion --
   }

ah, another hash function is defined here for use with the only defined Mask Generation Function, MGF1.

This - possibly different - hash function is used within MGF1 and therefore within PSS to provide the security required for MGF1.

Finally, a boring little constant for trailerField, so that we're complete:

   TrailerField ::= INTEGER { trailerFieldBC(1) }

Conclusion

OK, let's recapitulate: the signing algorithm is of course PSS, which depends on a mask generation function MGF1 as only option and a hash over the message. The MGF1 however also has a hash function algorithm assigned to it. Furthermore, you also can indicate a salt length - defaulting to 20 bytes - and a trailer field which currently just has one option.

Library design options

This message hash defaults to SHA-1, which is not secure for signing data. It also depends on a separate hash function used for MGF1, which also defaults to SHA-1. However, for MGF1 the hash function is actually secure. This unfortunately leads to different options for library designers:

specify one hash, and let this be the hash for both the message and the MGF1;
specify one hash, and let this be the message hash for just the message and keep MGF1 to use SHA-1;
always let the user specify both hashes, ignoring the fact that there is a default hash.

Commonly unfortunately either option 1 or option 2 is taken, leaving the developer guessing what hash is used for MGF1.

Encodings

OK, that was harder than it should be; let instead look at some options for encodings, using the online Lapo ASN.1 parser to decode the manually generated bytes.

First the one specified in the comments of the ASN.1 module within the standard:

   30 0D
      06 09 2A 86 48 86 F7 0D 01 01 0A
      30 00

which parses to:

   SEQUENCE (2 elem)
      OBJECT IDENTIFIER 1.2.840.113549.1.1.10 rsaPSS (PKCS #1)
      SEQUENCE (0 elem)

that's shorter then you'd expect. That's because the PSS parameters consist of a zero element sequence. This may sound weird, but it simply means that the default values are used, i.e. sha1, mgf1SHA1, a saltLength of 20 bytes and of course the only possible trailerField identifier, set to 1.

You can also specify the exact same structure without default values:

  30 3E
     06 09 2A 86 48  86 F7 0D 01 01 0A
     30 31
        A0 0B
           30 09
              06 05 2B 0E 03 02 1A
              05 00
        A1 18
           30 16
              06 09 2A 86 48 86 F7 0D 01 01 08
              30 09
                 06 05 2B 0E 03 02 1A
                 05 00
        A2 03
           02 01 14
        A3 03
           02 01 01

so this explicit encoding shows the actual structure. In above structure it is easy to replace the default parameters by different ones.

  SEQUENCE (2 elem)
    OBJECT IDENTIFIER 1.2.840.113549.1.1.10 rsaPSS (PKCS #1)
    SEQUENCE (4 elem)
      [0] (1 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 1.3.14.3.2.26 sha1 (OIW)
          NULL
      [1] (1 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 1.2.840.113549.1.1.8 pkcs1-MGF (PKCS #1)
          SEQUENCE (2 elem)
            OBJECT IDENTIFIER 1.3.14.3.2.26 sha1 (OIW)
            NULL
      [2] (1 elem)
        INTEGER 20
      [3] (1 elem)
        INTEGER 1

WARNING: beware that if a value has a default, and if the default value is being used then DER encoding specifies that it MUST NOT be encoded. So above is valid BER but not valid DER.

X.509 specifies that the signature field (of type AlgorithmIdentifier is in the TBSCertificate data (TBS means "to be signed", the data that is used in the signature calculation). The TBSCertificate data MUST be DER encoded. So above is not valid in a certificate.

Of course, as the numbering of SEQUENCE with defaults is explicit, generally it would be more logical to just specify the [0] and [1] parameters (tag encoding A0 and A1and leave the rest to the default).

So I would expect API's to generate e.g.:

  30 1E
     06 09 2A 86 48  86 F7 0D 01 01 0A
     30 11
        A0 0F
           30 0D
              06 09 60 86 48 01 65 03 04 02 01
              05 00

which parses as:

  SEQUENCE (2 elem)
    OBJECT IDENTIFIER 1.2.840.113549.1.1.10 rsaPSS (PKCS #1)
    SEQUENCE (1 elem)
      [0] (1 elem)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.16.840.1.101.3.4.2.1 sha-256 (NIST Algorithm)
          NULL

for SHA-256 as message hash and the default SHA-1 as MGF1 hash; the rest is set to the default values as well.

And, for the ones that uses the same SHA-256 hash for the message and MGF1:

  30 3C
     06 09 2A 86 48  86 F7 0D 01 01 0A
     30 2F
        A0 0F
           30 0D
              06 09 60 86 48 01 65 03 04 02 01
              05 00
        A1 1C
           30 1A
              06 09 2A 86 48 86 F7 0D 01 01 08
              30 0D
                 06 09 60 86 48 01 65 03 04 02 01
                 05 00

which parses as:

SEQUENCE (2 elem)
  OBJECT IDENTIFIER 1.2.840.113549.1.1.10 rsaPSS (PKCS #1)
  SEQUENCE (2 elem)
    [0] (1 elem)
      SEQUENCE (2 elem)
        OBJECT IDENTIFIER 2.16.840.1.101.3.4.2.1 sha-256 (NIST Algorithm)
        NULL
    [1] (1 elem)
      SEQUENCE (2 elem)
        OBJECT IDENTIFIER 1.2.840.113549.1.1.8 pkcs1-MGF (PKCS #1)
        SEQUENCE (2 elem)
          OBJECT IDENTIFIER 2.16.840.1.101.3.4.2.1 sha-256 (NIST Algorithm)
          NULL

this just leaves the salt and trailer field to the default.

Lamentation on default values

It might not come as a surprise that I'm not a fan of default values. They complicate the hell out of structures like this, and once you've chosen a default, such as SHA-1, it is pretty likely that you'll get into trouble as well, as SHA-1 should be considered broken by now. So we now have a provable secure padding mechanism that defaults to an insecure hash.

A slightly larger algorithm identifier that can be canonically encoded (i.e. has just one representation in bytes) and explicitly specifies the algorithms should have been preferred over the ASN.1 hell it is now. As stated above, the DER encoding requires to leave out values if they are identical to the default one.


Good Hash and making a bad hash It is obvious that there are different hashes.  I am looking for a reference on hash complexity as it relates to strength because I am considering making a "bad hash".  I have read a few things on the impossibility of making an efficient hash based on a block cipher, and then I thought that there are cases for bad hashes.  Here is an example of why I am considering this.

In hardware, you have a branch instruction.  The branch instructions that branch on memory address are a concern  If you can augment this memory address, you can leave the memory segment.  As a simple example, consider a BRANCH of 6, and this looks like

 BRANCH    OFFSET MEMORY
 1000      0110

It would be interesting to have a hash that results in some valid construct for a valid memory range.  The point of the hash is to not reveal the valid memory range.

BRANCH   HASH   OFFSET
1000     XXXX   XXXX

An interrupt would occur if the memory offset is outside the allowed hash.  The time available to calculate this hash would be small, so it could not be a good hash.

Is there a reference on complexity and strength so I might consider this further?

I don't believe a hash function would be a promising looking approach.

For one, you state that The point of the hash is to not reveal the valid memory range, however you really can't do it.  If the attacker can see the program (and knows all the inputs to the hash, except for the destination address), he can simply evaluate it for all plausible destination addresses, and see which ones the hash allows access to.  Even if there were as many as a billion plausible addresses (and that's a truly huge program), that's still quite feasible.

You also state that you're interested in indirect branches whose legitimate target is within a small range; one example where this may come up with the compilation of a switch/case construct.  However, the memory addresses this uses are typically stored along side the program space, and so if the attacker could modify those addresses, they could also modify the instructions themselves, and so adding protection to this case doesn't really add much real protection.

Of course, there are the larger case, where the branch could legitimately go to a number of different locations throughout the program.  Examples where this might happen include:

Function pointers
Object method invocations
Exception handling
Function return (which, from a CPU standpoint, is a branch)

These cases are much harder; a pure range-based check might end up being "somewhere within the program executable code", which isn't a great help.  Encoding the actual legitimate addresses within the hash is going to be on the same order of magnitude as the simple concatenation of the address list, and so that'd be slow (as the CPU will need to load a nontrivial fraction of that data structure to check if the branch is legitimate).

Now, there's been a lot of work in this space (that is, how do we make sure that program branches are as intended by the correct program); this specific approach doesn't look promising.


Applications of 3-collisions I recently read Improved Generic Algorithms for 3-Collisions by Joux and Lucks (Asiacrypt 2009), available as http://eprint.iacr.org/2009/305.pdf. I was wondering about applications of this technique (excluding of course the applications already given in appendix).
So my question is: Are there interesting applications (constructive or cryptanalytic, preferably practical) of this method that have been proposed since 2009 ?

There are more recent papers that cite Joux and Lucks.  Example: "Preimage Attacks against PKC98-Hash and HAS-V", Sasaki et al., uses the Joux-Lucks algorithm to attack two hash functions.

Have you looked at newer papers that cite Joux and Lucks?  Have you done a literature search, to find newer papers that cite their Asiacrypt 2009 paper?  Google Scholar, Citeseer, and Microsoft Academic Search can help you here.  That'd be a good start.  If someone uses the Joux-Lucks algorithm in their work, they'll probably cite the Joux and Lucks paper.


What are the potential (major) flaws in this security scheme? It’s been a few years since I read anything involving crypto. I’ve come across this scheme and I wonder how secure it is:

Alice generates an RSA keypair (we assume Alice is using proper random numbers).
Alice sends the public key as plain text to Bob.
Bob generates a 3DES session key: BA.
Bob sends BA encrypted with Alice’s public key, together with a checksum of BA.
Alice receives and decrypts BA using its private key.
All following sensitive data is encrypted with BA and integrity is checked via the checksum.
When the checksum fails communication is aborted and Alice generates a new keypair.

What are the potential (or very real) problems with this scheme?

One real problem is that lack of authentication between the two sides.  Here's one possible problem:

Alice generates an RSA keypair (we assume Alice is using proper random numbers)
Alice sends the public key as plain text to Bob.

Eve intercepts this message, and forwards on a message to Bob with her public key

Bob generates a 3DES session key: BA
Bob sends BA encrypted with [Eve]'s public key, together with a checksum of BA

Eve intercepts this message, and decrypts it with her private key, giving her the value of BA.  She then takes BA and the checksum, and encrypts it with Alice's public key, and sends that on to Alice

Alice receives and decrypts BA using its private key.
all following sensitive data is encrypted with BA and integrity is checked via the checksum.

That is, all sensitive data is encrypted by a key that Eve knows.  Furthermore, she can modify anything she wants.
In general, you cannot really have secure communication unless you know who you're actually communicating with.  In this case, Bob has no reason to believe that the public key he gets is from Alice, and not someone impersonating Alice.


Key Length & Hashing I need to use a hash function to generate a 128-bit key for a symmetric cipher. The specific cipher is from the eStream portofolio, called Rabbit.

I am using the SRP protocol for authentication (a type of EKE protocol). As a result of this, both parties will calculate the same large integer value and need to hash it into a key they can both use.

I would like to use SHA256 to generate the key, but its output is twice the length required.

Can I just truncate the hash to the lower 128 bits or something?

What is usually done in this case?

Short answer: just truncate, it's fine.

Long answer: you want a Key Derivation Function. A KDF turns an arbitrary-sized input (the shared secret obtained from SRP) into a configurable sequence of bytes, which you can split into as many sub-sequences as you need for symmetric cryptography. For instance, SSL/TLS defines a KDF (it calls it "PRF"; see section 5) so that it can extend the "master secret" (the shared secret obtained from whatever key exchange mechanism has been used) into six elements (an encryption key, a MAC key, and an IV, for each tunnel direction).

If you have a "reasonable" hash function such as SHA-256, and your secret data needs an amount of at most the hash output length, then a simple truncation will be an appropriate KDF. (Theoretically, being a good KDF after truncation is not implied by the hash function being appropriately resistant to collisions and preimages, but in practice you will not get any trouble with SHA-256 or SHA-512.)


Hashing user password without database to store salt I am building an Android app that will run purely locally on the user's device, no servers. It has a database that I want to encrypt with the user's password, which requires a 64 byte key. I've considered these 2 ways:

Use bcrypt, but that doesn't give me 64 bytes
Use SHA512 which is much faster to brute-force

The problem with both is that I don't have a reliable place to store a random salt.
The "attack scenario" would be someone pulling the database file off the phone and using a rainbow table to decrypt.

Should I:

add a static salt anyway?
use bcrypt and just fill the missing bytes with 0s, because it's more important that generating a rainbow table be hard?
use SHA512?
something else entirely?

BTW, rainbow tables are more thing of the past. They were time / space tradeoffs and currently rainbow tables of most plausible sizes can be generated in seconds by serious crackers - that is, they are not useful. Salt is still recommended to hide the fact when two people have the same password - but you are not using hashing for password storage, so unless you store the generated key hash somewhere, salt is not helping (you only have the encrypted database, not a hash of the password). One would need a rainbow table for all possible passwords in some set and all possible databases (within some constraints). Storage requirements would be insane. I wouldn't be worrying for rainbow tables if I understand the setup correctly.


AES with different modes of operation I'm taking up a cryptography class and this is for an assignment. We're asked to find the differences between AES/RSA in the different modes of operation vs the one timepad method.

From wiki, I can see that in all the different modes of operation(Eg CBC), the ek(encryption) is done. However, not much is said about what kind of encryption is used. What difference will it make if I use AES or DES in the encryption part in the process? I get that RSA is better than DES/AES dues to assymetricity. Apart from this difference, I can't figure out how the using just AES instead of DES would make AES with CBC would make it better than DES with CBC.
So, I read up and found this which says that the main reason why AES is better that DES is because of the key size. Is this the only difference?

Modes of operation are generally supposed to be independent of the underlying block cipher. They generally have a proof of security showing that the security of a system using said mode reduces to the security of the block cipher. However some modes, such as CTR, don't work well with block ciphers of short length (aka, old ciphers) and can leak information. Popular modes of operation should work equally well with all modern block ciphers.

You wouldn't use RSA in a mode of operation. Typically, RSA might be used to encrypt an AES key and AES would then be used in a mode of operation on the data.
AES is more secure than DES. There are attacks that leverage weaknesses DES's inner workings, while AES stands strong. AES also uses a larger block size (128 vs 64 bits), and small block sizes themselves have inherent weaknesses. Also, DES should not be used by itself, if used it should be used as TDES (triple-iterated DES) and TDES is very slow in software. (That's not a security feature, but it is a pragmatic issue.)

The provided link does mention the block size and speed issues. (And I think it was implied that DES was inherently weaker than AES, given that the question also asked about TDES (that is, DES iterated 3 times, which doesn't have the same weaknesses as DES).)

Briefly on RSA vs AES: They fulfill very different roles. RSA isn't "better" than AES, just useful in areas AES isn't (aka, asymmetric encryption). Conversely, RSA is much slower than AES and has many more caveats in implementation than AES, meaning it's easier to screw-up.


Padding schemes for asymmetric encryption with provable security in the standard model Most padding schemes for asymmetric encryption (OAEP, OAEP+) are only proven secure in the random oracle model.  Although no attacks are known, it would be nice to find a padding scheme with provable security in the standard model.  Are such padding schemes known?

To the best of my knowledge, there is no padded scheme for RSA (or general trapdoor permutation) that has been proven secure in the standard model. To be exact, let's call a padded scheme one where a padding transformation is carried out independently of the public key, and then the trapdoor permutation is applied once to the result.

Of course, as noted, we can do this to encrypt log(k) bits. However, for more than that, we don't know much. There is a very interesting result by Smith and Zhang that shows that under a "lossy" assumption about RSA, it's possible to prove security for about 1/4 of the bits of RSA. Concretely, you can encrypt 249 bits using a 2048-bit modulus. This is quite good.


Is there any code available online for CHA-1? Is there any code available online for the chaos-based hash algorithm CHA-1?
I am trying to apply the methodology of this paper to blockchain applications.

This is an obscure and not peer-reviewed article of dubious quality (I'm being polite). It has far too many flaws to list here. It should be best left ignored. The author did not publish a reference implementation, and the software they used is most likely just a proof-of-concept, not usable in practice.


Authenticated encryption with Signatures I've given a CPA secure private key encryption scheme (wich gets to a CCA secure scheme or better to an authenticated encryption scheme, when i combine it with a given MAC) and a unforgeable public key signature scheme. I want to combine both to get an authenticated encryption scheme.

My approach was to first sign the message and then encrypt(+MAC) the message with the signature. I think this should work.

But is there any possibility to combine the CPA secure private key encryption scheme with the public key signature scheme and get an authenticated encryption scheme, without using the MAC to ensure authenticity and integrity?

Mac AND Signatures seems like doing the same thing twice since encryption+mac leads to an authenticated encryption scheme. But i have to use Signatures in my scheme.

The   nonce || counter   version of CTR mode

satisfies the first two of the following conditions.

If

the symmetric encryption scheme is such that different ciphertexts

with the same nonce will decrypt to different plaintexts
and
the symmetric encryption scheme is secure against a single chosen ciphertext

whose nonce was not used for any of the challenge ciphertexts
and
the signature scheme is strongly unforgeable
and
the lengths of encodings of [message,signature] pairs don't reveal

any more about the messages than the lengths of the messages

then sign-then-encrypt will work for a single pair of users, but won't work with

signature verification keys from parties that aren't supposed to know the plaintexts.

I suspect that should generalize to arbitrary stream ciphers.


Using same keypair for Diffie-Hellman and signing Are there any security risks using a single key-pair for both key-exchange and signing?

I'm mainly interested in using Curve25519 for key-exchange and Ed25519 for signing. But similar combinations, such as EC-DH and EC-Schnorr or even EC-DSA with the same key pair would be interesting too.

Curve25519 hashes the output of an x-coordinate only Diffie-Hellman key exchange
Ed25519 is a slight variant of EC-Schnorr signatures.

I saw some recommendations to avoid using a single key for multiple purposes, but I couldn't find anything concrete.

The paper "On the Joint Security of Encryption and Signature in EMV" shows that ECIES and EC-Schnorr signatures can be used together without compromising security:

  In the random oracle model ECIES-KEM and EC-Schnorr are
  jointly secure if the gap-DLP problem and gap-DH problem are both hard

Ed25519 is extremely similar to EC-Schnorr, and both ECIES and Curve25519 are based on EC-DH, so this gives some indication that using both Curve25519 and Ed25519 with the same key-pair is secure.

Still a proof that directly refers to a keyexchange as used in Curve25519 would be nice.


Bridging the gap between security proofs and "real-world" security I've been studying cryptography for a little while. I understand fairly well the nuts and bolts of security proofs, but I'm having trouble reconciling the formal statements of security in these proofs with their practical "meaning" for a real system. Is there an intuitive way to reason about the "real-world" security of some cryptosystem based only on a formal proof of security against a constructed adversary?

As suggested in the comments, this question does seem broad and an answer would probably fill hundreds of journals. Nonetheless, the introduction to Katz & Lindell's Introduction to Modern Cryptography provides a nice starting point from a (largely) accepted perspective. Starting from a similar perspective, I'd say a provable security proof of some statement -- e.g., scheme S satisfies property P -- asserts nothing about the real-word beyond what is derivable about the real-world from the statement. This is incredibly limiting when you dig deeper, because many provable security proofs assert nothing about the real-world. That said, at least we can agree that the proven statement holds, rather than nothing at all.


For enciphering messages with AES in CTR mode, do I need a different key for each message? I have written a program to run AES in CTR mode with keys of 128,192 or 256 bits and checked it gives correct results with the data given in section F.5 at http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf

The program chooses a different nonce for each message that is enciphered. Do I need a different key for every message as well? or will a single key with a differing nonce provide all the security that is needed?

To fully answer your question, let me go over the exact way in which CTR mode works.  Following the diagram below:

CTR mode takes in a 96 bit nonce and a 32 bit counter that is incremented with each block.  This 128 bit value is then put through, let's say AES encryption, with either a 128, 192 or 256 bit key.  This same key is used with every block.  A 128 bit output from the AES encryption is produced and this value is then XORed with the first 128 bit block of plaintext.

Now, we have produced the first block of ciphertext.  This same technique is done for each block of plaintext using the same key, but simply incrementing the counter each time.  Due to this design, padding is not necessary for the final block of plaintext and each block can be encrypted at the same time in a parallel fashion.  You should never repeat nonce/key pairs, as this will make it very easy for an adversary to gain knowledge of information.  CTR mode is basically a key stream that produces an overall key to be XORed almost like a One Time Pad.

You may repeat keys for different messages, as long as the nonce and counter are different.


What would be a typical value for the security parameter of the Fully Homomorphic Encryption over the Integers scheme? The parameters of the Fully Homomorphic Encryption scheme by Dijk et.al are chosen according to the value of the security parameter ${\lambda}$, section 3 of the aforementioned article.

What is the security parameter for this scheme ? It represents the bits of security the scheme has ? If so, what would be a secure value right now ?

For the first part of the question, I couldn't find where the authors Quantify their security, what I understood that they build their scheme based on the hardness of GCD problem.

As for the second part, According to NIST recommendation which is a non-regulatory federal agency within the U.S. Commerce Department's Technology Administration. a secure value is estimated to be 112 and this won't be broken before 2030.  For other security estimates according to different schemes you can refer to https://www.keylength.com/


Is it safe to combine System.Random with cryptographically secure pseudo-random number generators? Have a look at the following codesample written in C#:

private static byte[] GetRandomBytes(int size)
{
    byte[] buff = new byte[size];
    // Create an array of crypto-secure random numbers
    using (RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider())
    {
        rng.GetBytes(buff);
    }

    // Gets a random byte from a non-crypto-secure RNG and xors each element with it
    // Alternatively, xor each element with a new random number
    int unsafeRand = (byte)_random.Next(0, 255);
    for (int i = 0; i < size; i++)
        buff[i] ^= unsafeRand;

    return buff;
}

Is it safe to combine the .NET cryptographically secure random number generators with an imperfect random number generator, for example via XOR?

Yes, if you XOR any values with a secure random numbers, you end up with secure random numbers.

You can easily see this by assuming the insecure random number is a constant instead. It only changes what the numbers are, it does not affect their relative probabilities.


Solve a system of non linear equations over GF I have the following set of equations:

$$M_{1}=\frac{y_1-y_0}{x_1-x_0}$$

$$M_{2}=\frac{y_2-y_0}{x_2-x_0}$$

$M_1, M_2,  x_1, y_1, x_2, y_2,$ are known and they are chosen from a $GF(2^m)$. I want to find  $x_0,y_0$

Does the previous set of equations is solvable?

And more...

If I have the following set of equations:

$$M_1=\frac{k_1-(y_0+(\frac{y_1-y_0}{x_1-x_0})(l_1-x_0))}{(l_1-x_0)(l_1-x_1)}$$

$$M_2=\frac{k_2-(y_0+(\frac{y_1-y_0}{x_1-x_0})(l_2-x_0))}{(l_2-x_0)(l_2-x_1)}$$

$$M_3=\frac{k_3-(y_0+(\frac{y_1-y_0}{x_1-x_0})(l_3-x_0))}{(l_3-x_0)(l_3-x_1)}$$

$$M_4=\frac{k_4-(y_0+(\frac{y_1-y_0}{x_1-x_0})(l_4-x_0))}{(l_4-x_0)(l_4-x_1)}$$

where $x_0,y_0 x_1,y_1$ are the unknown GF elements.

As Dilip Sarwate clarified the set of equations is constructed by someone who " chose three distinct x0,x1,x2, as well as y0,y1,y2, then computed M1, M2, and finally revealed $M_1,M_2,x_1,y_1,x_2,y_2$ but not $x_0,y_0$ to us" i.e. it is known that the system has solution.

My question was:
Can I recover the $x_0, y_0$ or in the second set of equations can I recover $x_0, x_1, y_0, y_1$ and generally in nonlinear sets to recover the respective $x_i, y_i$  by the provided info, on a GF? and the main point of my question: Does the fact that the set of equations is defined on a Galois Field impose any difficulties to find its solution?

I was not sure that it is possible to compute the solution of the  problem with the aforementioned parameters on a Galois Field.

As Dilip Sarwate stated in his answer the solution of the previous problem can be recovered for linear and nonlinear equations.

There have been extensive comments by the OP on this question as well as a related one and its answers and the consensus
don't seem to be converging at all to anything sensible.

  Broadly speaking, the field in which we are operating influences
  the answer to the question of whether a system of equations has
  solutions or not to some extent, but not in the ways that the OP
  thinks it does. Whether we are operating in a prime field or an
  extension of a prime field (what the OP calls gf or GF) has relatively
  little to do with the matter. In particular, for linear equations,
  the general theory of linear equations over a field
  usually has more to say about the matter than the identity of the
  field.

As Henrick Hellström has pointed out in a comment on the question,
the first set of equations in the OP's question can be converted
into a pair of linear equations in the unknowns $x_0$ and $y_0$,
say
$$\begin{align} a_{11}x_0 + a_{12}y_0 &= b_1\\
a_{21}x_0 + a_{22}y_0 &= b_2\end{align}$$
where the $a_{ij}$ and the $b_k$ are functions of
the known quantities $M_1, M_2, x_1, y_1, x_2, y_2$.
I refuse to calculate and state explicitly what the $a_{ij}$
and the $b_k$ are in terms of the known quantities. I will
differ from Henrick slightly, though, in that I do not think
that these equations are solvable for each and every choice of
$M_1, M_2, x_1, y_1, x_2, y_2$. This has nothing to do with
whether these quantities belong to GF$(2^m)$ or GF$(p^m)$ for
$p > 2$ or GF$(p)$ and everything to do with basic linear
equation theory: the matrix might be singular
for some choices of $M_1, M_2, x_1, y_1, x_2, y_2$ in which
case we get multiple solutions rather than a unique solution,
or the matrix might be singular and the equations might be
 inconsistent in which case no solution exists.

All this, however, as well as the OP's questions about other
equations is irrelevant in the context of Shamir's secret
sharing scheme which is referenced in the
other question
but not in this one but which I believe is the reason for
these questions.

If someone chose three distinct $x_0, x_1, x_2$, as well
as $y_0, y_1, y_2$, then computed $M_1$, $M_2$, and finally
revealed $M_1, M_2, x_1, y_1, x_2, y_2$, but not $x_0, y_0$
to us, then we can find $x_0$ and $y_0$ from the given
relationships, and inconsistency is not an issue.  Note the
requirement that $x_0, x_1, x_2$ be distinct which allows
the unnamed someone to avoid the heartbreak of
division by $0$ when computing $M_1$ and $M_2$.

Similar remarks apply to the nonlinear equations in the
OP's question as well.


How does CCM handle variable-length messages? Since CBC-MAC is insecure for variable-length messages if nothing is done to handle them, I'm wondering how it can be used with variable-length messages.

Rogaway's critique of CCM indicates that it is not an online mode of operation (the length must be known ahead of time for CCM). So, can it be altered/modified to be online? Like by perhaps appending the length of the message as the last block?

Q1: Since CBC-MAC is insecure for variable-length messages if nothing is done to handle them, I'm wondering how it can be used with variable-length messages.

CCM simply uses a packet format which simply includes the message size in the first block of data, see SP 80038C, to be precise section A.2.1: Formatting of the Control Information and the Nonce.

Unfortunately, including the length in the first block is what destroys most of the online capabilities. Furthermore, the packet construction is rather obnoxious, with a lot of bit fiddling and dependencies between different methods of length encoding, and so forth.

  Q2: Rogaway's critique of CCM indicates that it is not an online mode of operation (the length must be known ahead of time for CCM). So, can it be altered/modified to be online? Like by perhaps appending the length of the message as the last block?

Yes, it can be modified, but this is already done for you: it is called CMAC, usually prefixed by the cipher it was created for: AES-CMAC, particularly because it was designed for a block cipher with a block size of 128 bit:

  The core of AES-CMAC is the basic CBC-MAC.  For a message, M, to be
     authenticated, the CBC-MAC is applied to M.

CMAC consists of CBC-MAC with a pre- and post-processing added to it, particularly to avoid length extension attacks. It is possible to use AES-CBC and perform the pre- and post-processing yourself, which makes it a drop-in replacement for CBC-MAC even if CBC-MAC is accelerated.

There is a proposed AEAD cipher that replaces CCM as well, called EAX mode, which uses AES-CMAC to calculate the authentication tag. It was never standardized by NIST (and probably won't be, if you look at the time it has been a proposed mode) but it is a more flexible replacement of CCM.

Like CCM it only relies on the block cipher as underlying primitive but it is much more flexible and easier to handle as it doesn't require you to create "packets" like CCM mode does. Instead, everything is "online", with the disadvantage that it is - like CMAC - slower because of the pre- and post-processing required.

Both CCM and EAX mode are "two pass" AEAD ciphers, which means that all the data needs to be processed twice by the block cipher. There are modes of operation that can be faster: the single pass - but patented - OCB mode and the so called one-and-a-half pass GCM mode. Especially when accelerated (on newer Intel / AMD processors for instance) GCM mode will be faster than CCM or EAX mode, while only being slightly less flexible/online/foolproof compared to EAX mode.

The AES-CMAC RFC I've linked to is particularly based on XCBC MAC which was created by Philip Rogaway while EAX mode was specified here, which is co-authored by him. So he didn't just criticize fortunately, he did help to improve the situation as well.


Is it secure to use ciphertext feedback with RC4? Consider the following modification of RC4 to give some "ciphertext feedback"

i ← 0
j ← 0
C ← 0  -- We will remember the previous output ciphertext byte.
repeat
    i ← (i + 1) mod 256
    j ← (j + S[i] + C) mod 256  -- Use the previous ciphertext byte
                                -- for "ciphertext feedback".
    S[i] ↔ S[j]
    input P                     -- Read the next byte of plaintext
    C ← S[(S[i] + S[j]) mod 256] xor P
    output C                    -- Output the next byte of ciphertext

It would be nice to be able to use RC4 in some sort of plaintext-dependent mode like this, to avoid various stream cipher weaknesses while still having a cheap cipher that is easy to implement.

Is there something obvious (or non-obvious) that goes wrong here? [Edit: Other than my ability to write appropriate pseudocode on the first try.]

At least one thing goes very wrong: if an adversary can obtain the ciphertext for a few short chosen plaintexts and the same reused key/initial state, that allows reconstructing the state because the indexes vary in a controlled way. That certainly works if we obtain the ciphertext for the $2^{24}$ plaintexts consisting of the 3 bytes $u$ $v$ $w$ $0$ (basically, we can make some hyptohesis on a few state bytes, and confirm or rule it out based on the ciphertext for that chosen plaintext); or something on that tune. Likely, it is possible to mount an attack requiring much less chosen plaintext.

It might even be possible to mount an iteratively chosen plaintext attack working without key reuse.


Is it possible to make sense of an unknown language by means of cryptanalysis? I was wondering if it was possible to make any sense from an unknown language by using cryptanalysis. My premises are: suppose an analyst that knows nothing about a language (let's suppose chinese but it can be any other as long as it totally unknown to the analyst), but you do know it's a language (in order to avoid responses like codex seraphinianus) and you can have as much samples of the language as you want (imagine literature, tweets, newspapers, ...)

EDIT: This question came to my mind because I read some time ago about how Americans in WWII used navajo speakers to carry coded messages, hence my interest in trying to solve the problem by cryptanalysis. Also, I'm aware that navajo isn't a written language, but I wanted to assume it in my example for simplicity

If you've got many examples of a language then you can probably perform frequency analysis to distinguish correct plaintext from invalid plaintext. This would make it easier to find out if you have successfully broken a cipher.

Understanding the language itself is of course off topic here - language studies / linguistics different from cryptanalysis. But if you have a newspaper then you can put it next to another newspaper with a language you know. You'd certainly find many articles that would have the same content, so you can use these newspapers as a Rosetta stone and "decipher" (most of) the language.

AFTER THE EDIT: Yes, you could certainly perform - for instance - frequency analysis to establish which language constructs are used often and where. This can help deciphering the language. But I presume that it will only result in statistical knowledge of the text.

Finding - for instance - the meaning of nouns will not be helped too much with this kind of analysis, you need to place the language structures in context for that.


Why don’t all AES encryption tools produce the same key from the same password? Alice and Bob meet regularly. They have agreed face-to-face a 128 bit password which they want use to encrypt/decrypt emails written between them.

They decide to use 256-bit AES. Alice wrote her message, but found that every AES 256 application she used to encrypt her text provided a different ciphertext. She could not therefore communicate with Bob without specifying the tool that had encrypted her text, and she couldn’t check that the tool was genuine by comparing it with others.

Why is there seemingly no standard algorithm?
Why is there no simple and trusted tool (e.g. a javascript file) that can be downloaded and used offline for this purpose?

There are two things here:

Encryption uses mode of operation, and not "AES alone". Some of them are randomized by an initialization vector - that means the encryption of the same text under the same algorithm is still randomized and not deterministic. The encryption methods take care of that. You only need the correct key to decrypt.
Passwords are not keys. If you meet in person, you can create a real random key. That means each bit drawn independently from $\{0,1\}$, not just a password of a certain length, which can be found in any dictionary. If you want to use a password or a passphrase, then you are advised to use a proper key derivation function for passwords, e.g. PBKDF2, bcrypt or scrypt (most recommendations today go towards scrypt).

The problem with tools is, that if they just write "AES" on top, that doesn't mean they use the same mode or the same key derivation function inside. If they do, then the decryption will work. Still, there are non-deterministic modes, where it is an explicit goal, that the same message encrypted twice can not be distinguished from random gibberish.

All you can do is to actually test the tools available to you, if they work in conjunction. And you can stick to the verified, popular implementations. Never use some amateur implementation - never implement your own crypto.


Modular arithmetics in diffie-hellman Studying the basics of Diffie-Hellman key exchange, I'm stuck at a basic operation used in the end of the key exchange (where you show that both computations actually are the same). Can someone explain this step in detail?

(g^a mod p)^b mod p = (g^a)^b mod p

Where p is a prime and g is the primitive root to p

Thanks,

This can be derived from two simple facts about the $mod$ operation:

$a \bmod b = a + bi$ for some integer $i$ (for any $a, b$)

$a \bmod c = b \bmod c$ if $a - b = ci$ for some integer $i$

With these two facts, we can look at $(g^a \bmod p)^b$; that can be simplified to $(g^a + pi)^b$ (for some integer $i$), and by the binomial expansion, this is $g^{ab} + p(\textit{Other terms})$ (for some integer value of Other terms).

When we look at the difference between that and $(g^a)^b$, we get the value $g^{ab} + p(\textit{Other terms}) - (g^a)^b = p(\textit{Other terms})$, which is $p$ times some integer.

Hence, by our second fact, we immediate get $(g^a \bmod p)^b \bmod p = (g^a)^b \bmod p$, which is what we set out to prove


Generate $4\times 4$ Sboxes with a given branch number Say, I want to generate a lot of $4\times4$ Sboxes with linear (or differential) branch numbre of $3$. One idea is to take all the $302$ affine classes, expand each of those classes and check if any of the Sboxes has the desired branch number.

Is there any better way/known result (such as, this particular class does not contain any Sbox with linear branch number $3$) that can be used to reduce the search space?

The differential branch number is the sum of hamming weight between input and output difference distribution table (DDT). it is similar to linear branch number.

One way to construct S-box with branch number 3 is to use concept of differential-equivalence, DDT-equivalence and the $\gamma$-equivalence as shown in paper "Two Notions of Differential Equivalence on Sboxes".

The new paper accepted "Reconstructing an S-box from its Difference Distribution Table " provides algorithm to reconstruct S-box . therefore, you could apply the concept on  $\gamma$-equivalence DDT to find S-Box with branch number as you want.


Open-source usb TRNG and US standards - Help choosing I came across the ChaosKey and I remember the time I came accros the entrypy key that was always out of stock. I would really want one to play with, I would like the best open source I can get for under 80 USD.

According to Wikipedia, ChaosKey is FIPS-140-2 and FST-01 (NeuG) is NIST SP800-22 certified.

Now, I must say I don't care about US standard as I'm sure they lower them to make sure everything is NSA friendly. I would rather trust EU standard or something but it's not the norm apparently.

ChaosKey have an output of 10Mbit/s while NeuG (promoted by the Free Software Foundation) have an output of 602 kbit/s.

Now one could say better output mean weaker random numbers, or one is older than the other. So I'm a little bit lost here.

There is also the OneRNG, which output at 350 kbit/s and the BitBabbler White at 2.5Mbit/s.

I'm lost guys, help please.

Sorry if this isn't the right SE to post this, a the time it looked right.

If you fish around in your pocket, you can probably find one that costs 0.25 USD.

All it takes to use one of these gizmos is a little patience, a bit of hand-eye coordination, and some confidence that there aren't any surveillance cameras watching you, which you need anyway because you just typed in your password under them to decrypt your laptop's disk.

Once you've warmed it up by flipping it 256 times—or 512 times, just to be on the paranoid side, in case the entropy is ever so slightly below 1 bit per flip—you can get gigabits per second by using the outcome as the seed for an AES-CTR or ChaCha stream.

(You could even drive the cost down to 0.01 USD if you have the extra dexterity, but when the 0.25 USD option will still leave room in your budget for three or four nice dinners including booze, I figure the extra trouble of flipping a penny instead of a quarter isn't worth the 0.24 USD.)


Let $G$ be a PRG. Are the following $G'$ constructions based on $G$ necessarily PRGs? $G$ is a PRG where $|G(s)| > 2 \cdot |s|$.

$G'(s) = G(s0^{|s|})$.
$G'(s) = G(s_1...s_{n/2})$, where $s = s_1...s_n$.

My question here is whether my own proposed solutions are correct and do make sense.

Looks good to me! My intuition is that the PRG property means "random in, random out".

In 1. the input is not random so we get no guarantees - indeed, formally one could take any PRG H with 2s-bit inputs  and then define G to be H except on strings where the last s bits are 0, in which case G outputs the all-zero string. Now G is still a PRG, because the probability of hitting one of those modified points is at most $2^{-s}$ which makes a negligible difference overall. But $G'$ is now the function that always outputs the all-zero string.

What I've added here is the step from the intuition to a formal proof: I've given a case where $G$ is provably a PRG (ok, I didn't prove it here, but that's an easy exercise) and $G'$ is provably not a PRG.

In 2. if $s_1 \ldots s_n$ is uniform in $\{0,1\}^n$ then $s_1 \ldots s_{n/2}$ is certainly uniform in $\{0,1\}^{n/2}$. So applying $G$ to this string produces something uniformly distributed in the range of $G$, hence the whole thing is a PRG, just like you said.


Are SSH key-pairs an example of a zero knowledge proof? Quoting from source, authentication using SSH key pairs goes something like this:

  1) The client begins by sending an ID for the key pair it would like
  to authenticate with to the server.

  2) The server check's the
  authorized_keys file of the account that the client is attempting to
  log into for the key ID.

  3) If a public key with matching ID is found
  in the file, the server generates a random number and uses the public
  key to encrypt the number.

  4) The server sends the client this
  encrypted message.

  5) If the client actually has the associated
  private key, it will be able to decrypt the message using that key,
  revealing the original number.

  6) The client combines the decrypted
  number with the shared session key that is being used to encrypt the
  communication, and calculates the MD5 hash of this value.

  7) The
  client then sends this MD5 hash back to the server as an answer to the
  encrypted number message.

  8) The server uses the same shared session
  key and the original number that it sent to the client to calculate
  the MD5 value on its own. It compares its own calculation to the one
  that the client sent back. If these two values match, it proves that
  the client was in possession of the private key and the client is
  authenticated.

This seems to achieve all the necessary requirements of a zero knowledge proof. It is complete, sound, and the server learns no new knowledge of the user's private key.

I found this question that seemed related at first.

Is Using Digital Signatures to prove identity a zero knowledge proof?

However, the OP in this question required the Validator send a text, have the Prover encrypt it using their private key, and the Validator verify it using the public key. Thus some knowledge is being leaked (namely the private-key ciphertext and its corresponding challenge). Using the SSH key-pair protocol though, only the public-key ciphertext is being communicated, which is already public knowledge. As no new knowledge is being communicated, SSH meets the requirements of zero-knowledge proof, right?

At step 3-4), the server can use the protocol to decrypt any message encrypted with the public key of the client. The server is not able to decrypt alone because it does not know the secret key of the client, so the protocol is not perfectly zero-knowledge.
Moreover, the protocol is not a proof of knowledge because you cannot build an efficient knowledge extractor (see "validity"). At best, this protocol prove that the public key of the client is "well formed".


Verification of data on an untrusted remote storage server I was looking at tahoe-lafs which accepts a file, encrypts it, does erasure coding on it which generates n shares and then distributes it over the storage servers. The distribution is Share 1 = Server A, Share 2 = Server B and Share 3 = Server C.

Now If I want to make sure that the Server B  has that data, how do I go about doing that?

I could request the share, hash it and verify it by building a merkel tree but that would consume lot of storage server bandwidth if the share size is big. We can't ask the storage server to send us the hash by computing it since it might have the precomputed hash and might not generate the hash at all.

So how do I go about doing this? I looked at Provable data possession but couldn't understand much. Can someone point me in the right direction or help me understand it?

Proof of Data Possession (PDP) is a challenge-response protocol enabling a user (for example in the cloud network) to check whether a data file stored on a remote server is available in its original form or not. Data integrity is an important factor in almost any data and computation related context. It is not only one of the qualities of service, but also an important part of data security and privacy.

In PDP, data owners have a limited storage to store all messages so process their sensitive data to generate verifiable authenticators which are outsourced along with the data to the server (cloud). Although the servers promise a reliable environment to the users, the integrity of data is a subject to scepticism, as an untrusted cloud can easily be lost or corrupted, due to the existence of hardware and software failures or human errors.

In this point, data owners can download the entire message and check whether it is stored without any corruption or not. But it is not acceptable for users who have a limited capacity so PDP schemes provide a solution for data owners to check the cloud's claim for data storing.

There are different concepts for PDP schemes but share PDP amongst some servers is a good scenario for your question such as LINK.

On the purpose of reducing the hardness in the data owner side, Third Party Auditor is considered. When the data owner wants to upload the data on the server, calculates the tag corresponding to the message which has less size than the original message (Hash of message) and stores it. When he/ she plans to check the integrity of the message provide a challenge and get a response corresponding to the stored message from the server. Each PDP scheme should satisfy these properties:

•   Completeness: A valid proof generated by the server based on the protocol, should convince the TPA during the auditing process.

•   Soundness:  This property guarantees that for every untrusted cloud server, it is computationally impossible to generate an invalid proof that can pass the verification under the proposed scheme.

•   Perfect data privacy: The TPA is only trusted to check data integrity on behalf of users and should not learn any information about the data content. Perfect data privacy guarantees that nothing but the correctness of the proof is revealed to the TPA during protocol execution.


Is modulus a prime number important for non-symmetric cryptology? From this link
Generation of a cyclic group of prime order
we know how to generate a prime order group.

This illustrates why a prime order group is important.

But why is modulus a prime number also important?

In the theory of RSA, the modulus $N=pq$, and $\operatorname{totient}(N)=(p-1)(q-1)$， if we can find a factor $p'$ of $p-1$, then we can claim there is a $p'$ order sub-group? But it is not a modulus prime group, the $N$ is a composite number, is such a group useful?

Yes, such a group is useful. In particular, when $N= p\cdot q$ where $p,q$ are both strong primes (i.e. $p=2p'+1,q=2q'+1$ where $p',q'$ are also prime numbers).

Discrete logarithm in the prime order cyclic groups (order-$p'$ and order-$q'$) is believed to be hard. Such a group is called a group with hidden order.

A few examples of application: Fujisaki and Okamoto used this group to construct a commitment scheme. It has also been used in constructing a zero-knowledge proof of an integer falls within an interval (range proof).

Note that security does not hold for any arbitrary $N$ (even if it has only two large prime factors), see this paper.


Are there low-bit hashing or encryption functions for teaching cryptographical concepts? I understand how hashing and encryption/decryption work at a very high level, where the functions work as a black box. Hashing scrambles the input in a non-uniquely reversible way, whereas encryption uses a key to scramble the input in a reversible way where it's highly unlikely that any other key could produce the same output. Salts can be added to prevent rainbow attacks by randomising the output more.

Over time, collisions are detected in hashing functions, and encryption/decryption functions are cracked, leading to stronger functions being developed usually with more bits.

However, I would be interested in studying low-bit concrete hashing/encryption functions in order to understand how it can be mathematically proven to be uncrackable except by brute force (if that is indeed possible).

Are there any such low-bit functions that can be followed through step by step and analysed mathematically without the maths getting too complex? Ones that would be considered cryptographically secure except for their length?

Actually, lecturers/professors build simplified version of block ciphers and hash functions so that the students can understand better.
For Block ciphers there are;

Simplified DES by  Edward Schaefer in 96. You can also set it in Stinson's book Appendix G.
Simplified AES is first appeared on Cryptologia, 2003 by Musa, Schaefer, and Wedig.
Another Simplified AES Version again by Edward Schaefer
A Tutorial on Linear and Differential Cryptanalysis in 2002 by Hayes contains a simple SPN based block cipher to teach the Linear and Differential Cryptanalysis.

For hash functions;

Luhn Algorithm is a starting point.

A toy hash function  by Joshua Holden

In this paper I will discuss the requirements for a secure hash function and relate my attempts to come up with a “toy” system which both reasonably secure and also suitable for students to work with by hand in a classroom setting

Once  the Simplified version of AES is grasped, you can use them to build a hash function based on the Merkle–Damgård construction.

Also, this question Is there a simple hash function that one can compute without a computer? contains some others hash functions.


Is AES S-Box resistant to side-channel attacks? I know that implemntations with T-tables such as Golang's are prone to side-channel attacks, but is AES's S-Box wihtout any additional table also insecure ?

I assume the question is 'suppose you had an AES implementation that uses a precomputed SBOX table (and no other tables); can we do a key recovery attack using a timing or cache side channel?'
The answer to that question is "yes (at least potentially; we have to make some assumptions on the CPU hardware; at the very least, if it actually does have a cache)"
Here is a simple (and plausible) scenario where it is easy to recover some of the key bits (actually, we can recover them all, however that'd require more explanation)
Assume that we are on a CPU with 16-byte cache lines (that is, the cache stores things in 16 byte chunks; if the CPU reads in a location, the memory controller reads in all 16 bytes of that chunk).  We also assume that the sbox happens to be aligned at a 16-byte boundary (and so it occupies 16 cache lines) - actually, it'd be easier to exploit if it were misaligned; however for now, we'll assume aligned.
And, for our cached-based side channel, we can flush the cache, present a plaintext block, ask AES to encrypt it, and then check the cache to see which cache lines of the sbox were read in.  I'll cover the timing-based version of the attack below.
Here is how the attack would work: we flush the cache, and present a random plaintext, run it, and see which cache lines the sbox occupied.  The AES processing performs 160 sbox references (assuming AES-128); if we model each reference as random, then we have about a 1 in 2000 chance that there is some sbox cache line that is not referenced by any of the 160 reads.  Now, if (say) the cache line that corresponded to the 5X entries (that is, the sbox indicies with a high nybble of 5), then we can deduce that it was never refenced in the initial round; that is, for each byte $B_i$ of the plaintext and each key byte $K_i$, we have $B_i \oplus K_i \ne 5X$; that is, we can deduce what the high nibble of each key byte is not.
We can repeat this process until we've eliminated all possibilities for the high nybble of each key byte except for the correct one - this gives us half the key.  And, this would take maybe 30,000 or 50,000 probes (depending somewhat on whether we get to pick the plaintexts or have someone else generate random ones).  And, it's easy enough to recover the lower nybble as well (say, by relying on the second round sbox references); that would take more explanation.
As for how you would convert this into a timing attack (using the same base assumptions, except that the attacker cannot determine which cache lines are in the cache after the AES operation, but can measure the time), we can perform the same base attack, however before the AES operation, we set the cache so that 15 cache lines within the sbox are in the cache and 1 line is not, and then perform the AES operation.  If the 1 line is referenced, the CPU will read that line into the cache (which is an expensive operation; there's a reason CPU manufactures include a cache), and that would measurably increase the time.  By measuring the time, we can deduce whether that cache line was referenced, and hence we can proceed with the same attack (albeit with rather more probes required; we're getting data on whether a specific cache line was read, not data on all 16).


How to generate the exact AES key in both client and server side? I am using AES to create a secure tunnel for transmission of data.
As the symmetric key encryption will require the same key to encrypt and decrypt, so we need to generate the exact same key for the decrypt process. Is there any possible way for me to generate the exact same key for both side?

There are two main ways to have the same symmetric key on both parties:

key exchange using asymmetric crypto
generate the key from a known secret (eg: a password), such as using a password-based key-derivation function

The former is what you will find in TLS, where public key infrastructure is used to verify the other party's public key.
The latter is used in things like command-line encryption tools to derive a symmetric key from a password (and salt).
If you wish to setup a secure communications channel, your first choice should be TLS unless you have a very good reason not to use it.


What is cube attack and trivium cypher? Actually i am studying cube attack so there is some confusion regarding that in my mind this is

1- it is used for MAC KEY RECOVERY

2- It is a test that user performs to check the frogery or MAC or encryption

3- It is used to break encryption

4- cube attack have paper test like xor etc so they are performed for validty and consistency check

5- trivium cypher is encryption methodology of crypto so when they performed on that they decrypt the information to some extent

6- cypher text is encrypted string having data can cube attack is used to decrypt that

so regarding that above mentioned point can any body tell me where i am right and wrong and add some knowledge and tell me they are used some things correct about trivium cypher and cube attacks

Cube attack is the name given by Itai Dinur and Adi Shamir to a general attack on cryptographic schemes considered as multivariate polynomial equations, in their paper Cube Attacks on Tweakable Black Box Polynomials (in proceedings of EuroCrypt 2009). The origin and applicability of the attack has been challenged by Daniel Bernstein.

The attack aims at key recovery from plaintext/ciphertext pairs, with chosen plaintext. It is applicable to encryption and MACs using vulnerable block or stream ciphers.

For example, if one used a modified Trivium with only 767 initialization rounds instead of the prescribed 1152, the key could be recovered under a chosen-plaintext attack; that would compromise confidentiality and integrity of messages protected by that same key.

Thus, 1/3/5 in the question apply to some degree, for that modified Trivium.

It seems that 2/4/6 in the question do not apply (I'm reading 6 as trying to break encryption under known plaintext).

Addition following comment: In good practice, neither of 1/2/3/4/5/6 apply. A standard cipher design criteria has been (for over 20 years) to avoid the conditions that allow higher-order differential cryptanalysis to work; modern ciphers that survived analysis by competent cryptographers are thus practically immune to the cube attack (including AES in all key sizes and standard modes). As an aside, the cube attack requires chosen plaintext, thus typically does not apply if all that gets encrypted using a key is chosen by legitimate holders of that key, which seems to be the hypothesis made here.