How to use Real-Ideal model in a specific scenario (two party with cloud) I have designed a two-party protocol where two parties outsource their input to the cloud. For example, Alice and Bob have inputs $X$ and $Y$, respectively, after which Alice and Bob encrypt their input independently and then each one outsources the encrypted data to the cloud, independently. Afterward, the cloud performs homomorphic encryption on the encrypted data received from Alice and Bob and sends the result just to Alice.

My protocol is designed in the semi-honest model, and the cloud will not be able to learn anything about the parties' inputs nor the final result. Each party should not learn about another party.

My questions are:

In this protocol, how should I use the real / ideal model paradigm to prove the protocol's security?
Should I consider the cloud as a party who does not have any input and output?
Can I consider the following cases for the security proof of this protocol like this?

a. Alice is corrupted

b. Bob is corrupted

c. Cloud is corrupted
For case c in quesetion 3, how should the simulator simulate? The cloud will only see the encrypted data?

In this protocol, how should I use the real / ideal model paradigm to prove the protocol's security?

This question is too vague. Security in the real-ideal paradigm is defined as "for every adversary, there exists a simulator, such that the views are indistinguishable." So you have to do that.

  Should I consider the cloud as a party who does not have any input and output?

It receives/sends messages in the protocol, so you must do this.

  Can I consider the following cases for the security proof of this protocol like this?

Yes, but if these are the only cases you consider, then you are only proving security against a single corruption. In an $n$-party protocol, generally you would want to consider all cases of $n-1$ corrupt parties.

Your protocol is probably not secure against an adversary who corrupts both Alice & the cloud. I am inferring from your description that Alice has the decryption key to the encryption scheme, so when colluding with the cloud she can get Bob's input in the clear.

  For case c in quesetion 3, how should the simulator simulate? The cloud will only see the encrypted data?

The view of the cloud consists of the ciphertexts from the parties. You have to construct a simulator which generates something indistinguishable, given only the party's output from the functionality (this is the requirement for semi-honest security). In this case, I guess the cloud party gets no output from the functionality. So, given no information about the honest party's inputs, can you generate something that looks like encryptions of their inputs? Sure, just encrypt dummy stuff and use CPA security to argue that this simulation is indistinguishable.


Encryption using static AES256 symmetric key vs ephemeral session key For a hackathon I am designing an information exchange system for healthcare. Healthcare data is stored on unsecured systems. I want to assure confidentiality, integrity and authenticity of this data nonetheless. To allow multiple people to access the same data, I want to use a system like openPGP (without the email/HTML vulnerabilities), where I use an AES256 symmetric key (CBC, PCKS5 padding?) that is encrypted with RSA-2048 encryption using the public key of each authorized user.

The encrypted versions of the symmetric key will be stored with the data. New files will be added to the data over time, so I don't want to create a symmetric key per file, since revoking or granting access to a new user would mean we need to re-encrypt the symmetric keys of all files every time we do this.

To guarantee integrity and authenticity of the files, I want to sign them using the private key of one of the authorized uses using SHA256-RSA.
Public keys will be stored on a PKI, but public key validity will be verified in a face-to-face contact.

My question is two-fold.

What is the risk of using a static symmetric key for encryption vs a session key that changes each time? Is it purely the forward secrecy that ensures that if one session key gets compromised the other data remains safe? Or are there also other risks with not changing the symmetric key?
How good/bad is this setup in general? Any other problems I am overlooking in this setup? Other algorithms I should use?

What is the risk of using a static symmetric key for encryption vs a session key that changes each time?

Flexible access control: A big reason to use session keys is that it is easier to adjust your access control. It seems to me that the access for the files is not different. As long as that remains the case there is no direct need to use different keys to protect the data. However, with session keys you can make a different access control scheme without having to re-encrypt your data.
Access to the keys: remember that key management has a lot to do with the accessibility. It doesn't make much sense to use multiple keys if they are evenly vulnerable to attacks. However, patient information can get relatively large. It might be feasible to protect the master key better than the session keys that are required to decrypt large amounts of data.
Limitations of modes of operations and IV's: Modes of operation such as CBC do have limitations. If you would be encrypting large amounts of data then you might get into trouble in case the input of the block cipher repeats, as it would generate the same ciphertext block, and that would leak information to an adversary.
Forward secrecy: You already mentioned forward security, where the leakage of a session key doesn't compromise the confidentiality of data encrypted with other session keys.

What you could do is to encrypt the session keys with the master key. This may not feel more secure, but it does allow you keep the master key safe, possibly in a more secure system or device.

Another option that you could use is to use a key derivation function or KDF that derives session keys from the master key. That way the limitations of the mode of operation can be diminished. You may also use any kind of information rather than to use a specific IV. A KDF also solves the problem of the forward secrecy as you cannot derive the master or any of the other keys given a session key. This way you don't have to store any session keys; you don't however get the same flexibility as wrapping (encrypting) session keys.

  How good/bad is this setup in general? Any other problems I am overlooking in this setup?

That's a very broad question. I would not consider OpenPGP. Not so much because the protocol is bad, but it simply hasn't designed for this kind of operation. Furthermore, it is a rather old protocol which hasn't been updated to support the latest / greatest algorithms. More importantly, I don't thing the PGP method  of distributing keys does justice to a rather hierarchical setup used mainly at hospitals. X.509 may make a lot more sense.

RSA 2048 is not considered all that secure anymore, giving a security strength of about 112 bits. See keylength.com to see some comparable key strengths. Using it together with AES-256 gives you and your users a false sense of security. You may have to go for Elliptic Curve crypto and preferably an asymmetric Post Quantum Crypto algorithm to provide 256 bits of security. This may require long term security, after all.

With regards to algorithms, I think you should learn about new modes of operation such as AEAD modes of operation. Using AES-CBC is fraught with dangers; I would not consider CBC mode best of breed anymore.


Proof that in El Gamal DDH implies CPA I am refering to the theorem:

  If the Discrete Diffie-Hellman problem is hard (i.e. if the DDH assumption holds), El Gamal is IND-CPA secure."

which is stated here along with the proof.

So we have adversary A that has a non-negligible advantage with CPA and we are trying to build adversary B that can break DDH.
B is given $a$,$b$,$c$ which could be $g^x$, $g^y$ and $g^{xy}$ or $g^z$.
Then A outputs $m_0$,$m_1$ to B which encrypts by picking random $b$ and returning to A: $c_0=b$, $c_1=c*m_b$

Now if $c=g^{xy}$ then A will be like interacting with real encryption oracle. Otherwise they say it will be like receiving random values

What I couldn't understand, is that since $c=g^z$ where $z$ is randomly chosen, assuming order of group $q$ which is prime, then there is always $k$ such that $z=k*y\ (mod\ q)$. So even when the B is given $g^z$ the encryption of the message could be a valid el gamal encryption, so it shouldn't look that random to the adversary A.

Is that right?

EDIT:

So apparently, as pointed out by fkraiem, since the adversary is given the public key $g^x$, when $c_0=b$ he expects the encrypted message to be: $c_1=g^{x\cdot y}\cdot m$ not just a random $k$. The probability of $k=x$ is negligible.

A key point is that for group $G$ and any arbitrary $m \in G$, choosing a uniform $k \in G$ and setting $\hat{k} = k \cdot m$ gives the same distribution for $\hat{k}$ as just choosing it uniformly from $G$.
This is because:
$Pr[\hat{k}=k \cdot m] =Pr[k=\hat{k} \cdot m^{-1}] = {1 \over {|G|}}$
So in the reduction, when $A$ interacts with the challenge $<u=g^y,v=g^z \cdot m>$ for random $z$, $u$ is completely independent of $v$, and so they reveal no information over each other.
Notice that even though it's not a valid encryption scheme (because it's impossible to decrypt), the experiment is still well defined.


ECDSA security using same per-message secrets $k$ but different signing keys I know that when I have a ECDSA keypair and use it twice with the same $k$ to sign different messages then the private key can be recovered.

If I now have multiple ECDSA keypairs and sign a message with each, and use the same $k$ in each signature, is this still secure?

Note: The signed messages may be identical.

I personally see no problem with it and the math seems to support that in my opinion, but better safe then sorry. This is why I'm asking the question.

For ECDSA the per-message secret $k$ should be generated randomly. In particular you have to ensure that the per-message secrets never repeat, or else the private key $d$ can be recovered. First, let's have a look at an example where the same per-message secret $k$ and the same private key $d$ was used to generate ECDSA signatures $(r, s_1)$ and $(r, s_2)$ on two messages $m_1$ and $m_2$. Then $s_1 \equiv k^{-1}(e_1+dr)$ (mod n) and $s_2 \equiv k^{-1}(e_2+dr)$ (mod n), where $e_1 = H(m_1)$ and $e_2 = H(m_2)$. Then $ks_1 \equiv e_1 + dr$ (mod n) and $ks_2 \equiv e_2 +dr$ (mod n). Subtraction gives $k(s_1-s_2) \equiv e_1 - e_2$ (mod n). If $s_1 \not\equiv s_2$ (mod n), which occurs with overwhelming probability, then

\begin{equation}
k \equiv (s_1 - s_2)^{-1}(e_1 - e_2)\mod{n}.
\end{equation}

From this an adversary can determine $k$, and then use $d=r^{-1}(ks-e)\mod n$ to recover the private key $d$. This implementation failure was used, for example, to extract the signing key used for the PlayStation 3 gaming console or in 2013 to rip users of Android Bitcoin Wallet off their funds.

Now let's have a look at a second example, where the same per-message secret $k$, but different private keys $d_1$ and $d_2$ $(d_1 \neq d_2)$ are used to generate different signatures. In this case the subtraction step from before would lead to $k(s_1-s_2) \equiv e_1-e_2+r(d_1-d_2) \mod n$. From this you are not able to recover the private keys $d_1$ and $d_2$ used to generate the signatures $s_1$ and $s_2$ unless you can efficiently solve the $ECDLP$ (assuming an adequate elliptic curve group was chosen). If you signed the same message, i.e. $m_1=m_2$, then $e_1-e_2$ would cancel out, but this doesn't give the attacker any more advantage as $e_1$ and $e_2$ are supposed to be known anyway.

But be aware that as soon as you’d use the same private-key / message-secret pair to sign another message, this would lead us back to the scenario depicted in the first example. This means that you’d have to be 100 % sure that you only need to sign one single message using the same $k$/$d$-pair. In practice however, you normally don't create a new ECDSA key-pair for every new data you need to sign, as

for every new key-pair you create the verifying party will need to learn the new corresponding public key
you need to keep track of which key to use for every piece of data you signed if you are both the verifying and signing party
using some crypto APIs you sometimes cannot control the per-message secret but only the private key and the signing function will create its own per-message secret making use of the underlying CSRNG


Passing data securely through QR codes? We have to implement a way to securely transfer data from a POS to a mobile app using QR codes.

The mobile app gets the payment parameters (amount, description, purchase_id, store_id) to create the payment intent by scanning a QR code generated from the POS,
the app passes the info to a trusted server through an API and
if the payment succeeds, it generates a QR code for the POS, including some parameters the store needs to match the payment back in the POS system.

We need to make sure that the system is secure so is not possible for an attacker to fake these QR codes.

Would this ensure the system security?

The trusted server generates a key pair and a shared secret
The commerce (POS) generates a key pair
The trusted server and the POS exchange their public keys and the shared secret
The QR code contains 2 parts: an encrypted body + signature
The encrypted body is a JSON string encrypted using the server’s / POS’s public key. The only way to decipher the body is using the private key so the structure of the message remains unknown.
The signature is a HMAC-SHA256(body, shared-key). So we can verify the integrity of the body once decrypted in the server or POS.

Does this make sense?

If the POS system is online, then its simple. Just have a purchase ID in the QR.
The POS will call your API, and "create" an unpaid purchase.
This purchase ID is encoded into an QR.

Then the customer scans this QR, and approves payment. You don't even need to display a returning QR, because the POS could poll the API at regular intervals and check when the ID is "paid".

If you want to be able to have an offline POS, its also pretty easy. You need a shared key, that is unique per physical store location (store_id must also be unique per store location, store_id is then used by the payment server to look up the correct HMAC key).

If a store accidentially leaks their shared key, they must replace it immediately, else they risk customers creating fake QR codes to get products for free.

The store have a QR code with:
amount + "-" + description + "-" + purchase_id + "-" + store_id + hmac_sha256(amount + "-" + description + "-" + purchase_id + "-" + store_id + "-unpaid-", SHARED_KEY)

You send this to server. Server validates the hmac, and then, upon payment, creates the following QR:
hmac_sha256(amount + "-" + description + "-" + purchase_id + "-" + store_id + "-paid-", SHARED_KEY)

Assuming a shared hmac_sha256 key of: SHAREDKESHAREDKESHAREDKESHAREDKE

First you create the purchase:
100-USB memory-0001-1212-475d1fa90f24e134e76ffcc075ad3e7ce2c76e1ae78c7c8408c7508882ee9952
(89 characters)

Then app sends this for payment.
When payment is done, you create the following QR:
0899dd28bb8e5cfe6d54deb0000df01cec88f65b85a0b4148d7b49dddd2453d9
(64 characters)

NOTE: The original purchase data is NOT needed in the "reply QR" - the cash register already have this data from the pending transaction, that it can use to check the reply QR. So the "reply QR" becomes much smaller and more easier to scan.

NOTE2: Even if someone learns the structure, its still a impossibility to create a valid reply HMAC from the request HMAC. Changing "-unpaid-" into "-paid-" would require knowledge of the shared key.

NOTE3: purchase_id must be unique among a single physical store location (store_id). If a store is generating duplicate purchase_id's, a customer can reuse a paid order to get products for free. If a store location has multiple offline POS not even connected with each other, the store, which also chooses purchase_id, must prepent the POS location to purchase_id, eg have purchase_id 10000-19999 for POS 1, 20000-29999 for POS 2, and so on. In my solution, purchase_id can be of any length required for the purchase_id not to roll over.

You really don't need to mix in RSA at all.

Actually, you don't need an HMAC for the request at all (but its ALWAYS required for the Response). Its just a customer protection so any scan errors or any sheninigans doesn't cause a customer to do a payment for a non-existing purchase.
The reason is that the request isn't security-sensitive, is because if the customer edits the purchase request, the response QR for the paid purchase will not validate, and the hacking customer will not get anything out of it.

But you must atleast have some error protection so not a damaged QR display or strong light falling on QR-code or the phone camera causes it to generate a purchase request, which when paid for, will not release any products, and thus cause a legit, fair customer to lose money. Thats extremely unlikely however, as QR code contains their own checksums, but feel free to add any checksum you like to the request. It can be HMAC, a md5 hash, a CRC32, whatever. Even a truncated hash suffices, if you must keep the request size down to not cause too large (and unscannable) QR codes.

The customer editing a purchase request to for example try to get products cheaper, and then getting a invalid response QR back, would be equvalient of a customer taking a 20 dollar bill, and trying to make a 100 dollar bill out of it, failing the fraud attempt, and thus losing the 20 dollar bill. So basically, any protection on the request is only for customer protection against themselves, which you can skip if your situation does not require it.


What are the implications of a non “constant time” implementations on trusted systems in a non-network scenario? Assume a scenario where a symmetric encryption algorithm (for example: AES) wasn't implemented in a way it would safeguard against timing attacks. This symmetric encryption implementation is only used locally to encrypt/decrypt data.

The only time that data is passed via a network (if at all), it is done so as pre-encrypted data (read: as locally created ciphertext). Yet, network transport itself is implemented differently, uses SSL, and doesn't have any constant time issue. Practically this means that if, the locally created ciphertext passes the wire in a – let's just call it – double-encrypted form. So, let's not focus on network transport, but rather on the core of the scenario which I'm asking about: the local, non-network part where data is encrypted/decrypted locally using a different, non constant time implementation.

In the above scenario, it seems as if timing attacks aren't much of an attack vector unless we assume trusting local systems might be a problem, which – in this scenario – can be ruled out as the local systems are trusted (think along the lines of a Sensitive Compartmented Information Facility).

To be sure I'm not missing something due to limiting my thoughts too much on network-related timing attacks:

What are the potential implications of a non “constant time” implementations on trusted systems in a non-network scenario, if any?

Differently put:

If we assume the local, non-network encryption/decryption to be handled by trusted systems in a compartmented facility, do we still have to worry about implementing that local encryption algo in constant time? If so, what are the attack vectors we're trying to cover by doing so?

"Constant-time" is about not leaking information through timing-based side-channels. If you assume that there is no side-channel, then, in particular, there is no side-channel attack. It is nevertheless a rather bold assumption.

There is a large variety of possible side-channels, and lab demonstrations of attacks have been done exploiting, among others, power usage (especially through differential power analysis), electromagnetic emissions, sound,... Most, though, require the attacker to be in the physical vicinity of the target systems (the actual operating distance may vary, e.g. up to a few dozen meters for sound-based attacks). Timing attacks are special in that respect, since, thanks to the magic of the Internet, they may be exploitable from very remote attackers.

If there is no network, then attacks will be geographically constrained, and thus physical protection measures (isolated building with guards) should be effective. So, in effect, your question really hinges on whether the target system is really "compartmented". As illustrations, consider the following:

Some of the demonstrations of timing attacks have been across virtual machines: the attacker and the victim run in two different VM that merely happens to be cohosted on the same hardware. From an abstract point of view, the isolation contract of the VM is fulfilled; and still, the keys flow.
Not leaving physical tracks is incredibly difficult. For instance, it is possibly to listen on conversations held in a room from a large distance, with a laser microphone: a reflective surface (e.g. a window) vibrates in response to the sound waves, and such vibrations are picked up with interferometry. Theoretically, this kind of listening should work with acoustic attacks.
Electrical activity may leak over power lines. A nominally non-networked system may still send considerable information, unwittingly, over its power cable. This can be fixed with isolation transformers, but ascertaining that such transformers are in place where they should can be quite difficult.
Ultimately, systems are never completely isolated: at some point, some result should exit and have a physically observable effect; otherwise, whatever the system does becomes irrelevant, from a philosophical point of view. Therefore, the overall processing time is available. Then it is a matter of quantifying the precision of the measure.

Thus, in practice, having a non-constant-time AES implementation can be guaranteed not to be an issue only in usage contexts where true physical compartmentation can be shown to be applied, and, in particular, where the ultimate "networking" happens in human-compatible time (i.e. in a matter of days, not microseconds). This tends to be the kind of context where performance is not an issue, thereby removing the most common excuse for using non-constant-time implementations.


Secure logical AND using Ishai-Sahai-Wagner Scheme I want to try to implement a secure AND the way it was described here:
https://eprint.iacr.org/2010/441.pdf

It says that there are two bits a and b and that they have been split into d+1 shares. How can I split a bit? I guess there isn't something more atomic than a bit, isn't it? Can you give me an example on how to do this?
I mean I could say that, for example:

Let $d$ be 4. Assume that $a$ = 1, then I can split it into the following 4 shares: $a_1 = 1, a_2 = 1, a_3 = 1, a_4 = 0$ because then it holds that $1 \mathbin{\oplus}1\mathbin{\oplus}1\mathbin{\oplus}0 = 1 = a$. Is that what is meant with the $d$ shares? I assume these shares are random values?

I tried a first implementation of the secure AND as follows:

void SecAND(char a, char b, char* arr, char* brr)
{
  int i; int j;
  int d = 4;
  int r[4][4];
  int c[4];
  for(i = 0; i < d; i++)
  {
      for(j = i+1; j < d; j++)
      {
          srand(time(NULL));
          int rij = rand() % 2;
          r[i][j] = rij;
      }
  }

  for(i = 0; i < d; i++)
  {
      for(j = i+1; j < d; j++)
      {
          r[j][i] = (r[i][j]^(arr[i]*brr[j]))^(arr[j]*brr[i]);
      }
  }

  for(i = 0; i < d; i++)
  {
      c[i] = (arr[i]*brr[i]);

      for(j = 0; j < d; j++)
      {
          if(j != i)
          {
              c[i] = c[i] ^r[i][j];
          }
      }
  }

}

Can this be correct?

"Splitting into $d + 1$ shares" is mentioned in the Introduction, right after a reference to secret sharing schemes and mentioning threshold property. So, this particular IACR preprint is not the best source on secret sharing. I'd suggest to start from Shamir secret sharing algorithm.


Partial decryption of large file in AES-GCM (or other modes)? Lets assume

a 4gig file that is internally made of 1 million pages of 4k bytes each (page).
the file was originally AES-GCM encrypted
these pages (or entire file) lives across the internet i.e. individual page reads are expensive/slow. (network IO operations are at page level by the way)

Is there any way to decrypt the 1,000,000th page without first fetching the 999,999 pages? I think not because the mac in GCM needs to 'digest' all the data that was encrypted, right.

The only other scheme I can think of is performing encryption/decryption at a page level but then we'd have to store 28 bytes extra (128 bits IV + 96 bits tag) for every page. One could argue 28MB overhead for a 4GB file isn't much but I'm trying to minimize overheads.

I would love to see if someone has a better design proposal for this situation.

Sure, basically GCM is counter mode encryption with an authentication tag added. You can encrypt any part of the stream without issue if you know the key and the counter for that part. Obviously, you cannot check the integrity though, because the tag is the integrity of the entire file.

Basically, you only have to perform the top part of the scheme:


Cryptography math requirements I know that most of the math related to cryptography is number theory/abstract algebra/probability, but I was wondering if there are some algorithms that make use of other fields of math like real/complex analysis, differential equations or linear algebra?
Also, what is highest level of mathematics required for cryptography?

It would be hard to find a category of mathematics not related in some way to cryptography, here is a list of applied mathematics by subject area. Even very abstract mathematics could be future cryptographic tools waiting to happen:

"A large part of mathematics which becomes useful developed with absolutely no desire to be useful, and in a situation where nobody could possibly know in what area it would become useful; and there were no general indications that it ever would be so. "


Key generation algorithm based on bytes in a drive I am a novice cyber security student and thought of a way to generate a random cryptographic key.

The algorithm works as follows:

Get the size (in bytes) of every file in a directory (drills down into each folder to only get files)
Concatenate each byte sizes together, EX: A file length of 2 bytes and a file length of 4 bytes would would make "24"
This creates a string thousands of digits (I've done up to 10,000,000 digits long)
If the user needs an extra long key, hash each individual character using SHA-256
Take the final string (millions of bytes) hash it down to two 64 byte hashes and combine them to make a 128 byte or 256 byte based on user selection.

Some reasons I chose this method include the randomization of the string created since it's very unlikely that two people would have the exact same drive structure, and the size of the bytes hashed to make the key grows very rapidly since most files are several hundred bytes or more.

I guess this isn't a very direct question, but does this algorithm sound useful/secure? What are some ways I could improve on this algorithm?

Useful: No. Secure: No.

The most pertinent part of your question is the title which I'd slightly correct to "Key generation algorithm based on file lengths in a drive".  It is here at the start that you've made invalid assumptions. There are others later on too though.

A random cryptographic key is essentially entropy, which you can read as uncertainty.  So from a high level, key = entropy = uncertainty.  The file structure on a typical machine is fairly well specified, whether it's a proper *nix machine or one of those other ones. If the machine is newly created (especially as a virtual image or embedded), the file layout may be identical between machine instances.  So any key derived from the file system (lengths or contents thereof) will be highly predicable.  There for insecure.  You have confused complexity with uncertainty.  The file system is certainly complex, but think of all of those free AOL CDs that ended up as coasters.  If you had run your algorithm across the newly installed AOL directory, all of the generated keys would be identical across any machine you'd just installed on. All of you  10 million digit concatenations would have been identical, or very nearly identical.

The second error is the key length.  As a security student, you'll come across typical acceptable key sizes.  No one will even require more than 256 bits of key security. There are mathematical proofs of this limit.  Your attempt at creating an extra long key is meaningless. A lot of cryptographic primitives are designed around the 256 bit size.  What were you attempting to use a 10 million byte key for, as there is no legitimate function to absorb such a key? [You're not thinking one time pad are you?]

With respect, you're probably quite new to cryptography on the basis of this question. There is no effective improvement that can be made to this algorithm without a much more extensive understanding of the nature of a cryptographic key and it's relationship to entropy.

You are though ultimately correct in realising that a key can be generated from the chaotic churn inside a modern computer environment.  Chaos principles can be applied to a file system and there is true entropy but it requires a much greater understanding of the principles before you can extract it safely.


What is the difference in designing an MPC protocol by ring or field? To the best of my knowledge, most of the MPC protocol's are built on a ring $\mathbb{Z}_{2^\ell}$(usually $\mathbb{Z}_{2^{64}}$) or field $\mathbb{Z}_p$ ($p$ is a big prime), why? What is the difference between them?
Examples:

Ring examples such as ABY, SecureML.

Field example such as SecureGWAS.

Update:
This paper says that SS-MPC over the ring cannot easily construct the constant-round protocol due to a lack of the multiplicative inverse.

[...][Most] of the MPC protocol is built on a ring $\mathbb{Z}_{2^\ell}$(usually $\mathbb{Z}_{2^{64}}$) or field $\mathbb{Z}_p$($p$ is a big prime), why?

The relevant protocols for $\mathbb{Z}_{2^\ell}$ most likely use boolean sharing / boolean garbled circuits (representing each individual bit as a shared value) whereas the ones for $\mathbb{Z}_p$ use arithmetic sharing and in some rare cases arithmetic garbled circuits.
The core difference between these two is the set of operations that can be performed cheaply on each:

Bit-wise XOR tends to be extremely cheap with boolean sharing but is usually prohibitively expensive with arithmetic ones
Normal addition is not too-expensive for boolean sharings but tends to be free for arithmetic ones
Bitwise / -oriented gates and reductions in general tend to be much cheaper for boolean sharings than for arithmetic ones - e.g. equality comparisons or bitwise operations commonly seen in symmetric ciphers
Arithmetic operations tend to be much cheaper in the arithmetic case, especially multiplication which is a primitive operation there but requires $O(\ell^2)$ ish non-free operations for boolean sharings


How long would it take to calculate the hash of a password by hand? Suppose one had no computer (or rainbow tables), but had access a pen and paper as well as all the necessary documentation for modern (best practice, not outdated) hashing algorithms and mathematical formulae.
How long would it take to compute the hash of a password?
Define password

a random 8 character string of characters (numbers, letters, allowable symbols)

Define best practice

bcrypt (or similar) with calculation performed n=10 (so 1024 times total)

If you want a "quick" way of determining how long it will take for bcrypt-n10, you can process by hand a very very VERY small subset of its calculation, then multiply that time by how many times the algorithm will use it.
The round function is used many times, you can perform components just once to get a base time. There are operations on 32-bit values, you can just do 1.
There are 3072 round operations after key setup (64x16x3)
There are 521 round operations per expand key
There are 539 32-bit XORs per expand key
There are 2048 expand keys per key setup
That gives you 1070080 round operations and 1103872 32-bit XORs
A round contains 2 XOR and 3 32-bit addition operations and 4 S-Box lookups, you can now break this into:
3,210,240 unsigned 32-bit additions
3,244,032 32-bit XOR operations
4,280,320 S-Box lookups (which change all the time)
64 blowfish key schedule operations (ignore, maybe it will add 3% to the time)
Moving tons of data around
If you were SUPER fast and could do an XOR in only 10s, an addition in only 20s, and an S-Box lookup in 10s, that is 4842 days calculating 8 hours per day, just for those operations.
You would still need to take into account how much paper it would take, transferring data from page to page when full, and the additional writing required, and the additional verification of operations to make sure you don't make a 1-bit mistake somewhere and screw the whole thing up. Just go ahead and double the time.
That is 26 years working 7 days a week or 37 years working 5 days a week.
It would probably take me at least that long to do it even if I had an electronic calculator that had hex input and an assistant or apprentice helping me to expand s-boxes and verify my work; there is no way my fingers could do that much work a day or work that quickly.
Out of the 365 million or so bit operations you need to perform, the allowed error rate is 0. How much extra effort would it take you to make sure you make no mistakes in calculation over the course of decades? So try it out, get 2 random numbers, do one addition and one XOR, and see if the numbers line up... or if it takes you more time.


What is the practical relevance of the wordsize when using a Hash? I understand that the word size is the internal "working package size" below the block size of a cryptographic hash function (and a block cipher), as each block is broken into words an than processed round-based. Does this size have any practical relevance when using that function? For instance do algorithms with 64b word size perform better on 64b machines? Or does aligning the message-to-hash at the word size have any impact?

Yes, the internal word size of a hash algorithm has some significance, pretty much for the reasons given in the question.

Algorithms with 64-bit word size have a (typically sizable) performance edge on 64-bit machines (more precisely: for large messages, and comparable implementations, the ratio of the number of bytes hashed in a given time over that for a comparable algorithm with 32-bit word size will likely be significantly higher using a 64-bit machine and making good use of the architecture, than this ratio is on a 32-bit machine). For this reason we have SHA-512/256, a 256-bit hash obtained by truncating to 256-bit a natively 512-bit hash with internal 64-bit word size: on a 64-bit machine, SHA-512/256 can be faster than SHA-256, a natively 256-bit hash with internal 32-bit word size. See this for more details.

And, on most machines, there is some (typically small) performance penalty if the message to hash is not aligned to the native word size.


How can I tell which curve a given ECDSA implementation uses? (P-521 or something else) I'd like to test and see if certain software uses P-521 ECC curves, or if it uses another variant.

Without having access to the sourcecode, or the specification, is there any way for me to test which ECC curve a given implementation of software uses?

Take a x509 certificate as an example, aside from ASN.1 information that may exist in the file, is there any way to look at raw cryptographic outputs and determine the curve used?

What is the minimum information needed to understand what curve is being used?  (What variables on the client, or on the issuer/CA are needed)?

Signatures make sense only if there is a verifier somewhere, and the verifier uses the public key, which is public. The public key will normally include the unambiguous specification of the curve. If the public key does not include such a specification (e.g. a closed system where both signer and verifier know a priori the curve), then you can still infer things:

A public key is a curve point $(X,Y)$ which fulfils the curve equation $Y^2 = X^3 + aX + b$ where $a$ and $b$ are part of the curve definition. This allows you to match the public key point with some standard curves.
If point compression is used, you might have only the $X$ coordinate. You can still match that with standard curves, because $X$ is part of the base field on which the curve is defined. If you find a $X$ which is a 521-bit integer or not much smaller (e.g. no smaller than 500 bits) then chances are high that the curve is P-521. Although it could be a custom non-standard curve of the same size.
If you only see the signature themselves, then you can still try to match that to standard curves. An ECDSA signature is a pair of integers $(r,s)$, where both $r$ and $s$ are in the $1..q-1$ range, $q$ being the size of the curve. There again, if both $r$ and $s$ are in the 500 to 521 bits, then chances are that the curve is P-521, because $r$ and $s$ would be too large for the smaller curves (the previous ones are 401-bit only), and it would be very improbable to obtain both values below 521 bits if the curve is B-571 or K-571 (the next ones, among the standard curves).


Is this schema secure? I want to know if we use function H as random oracle in RSA Blind Signature and assume that RSA Assumption is correct, is it true that the RSA blind signature schema is secure?(i.e. There isn't any adversary who can create a valid signature on a message that he doesn't queried to signer oracle). Intuitively, I think this is true, but I can't prove it formally. Does anyone have an idea?

Blind signature works as follows:

(1) User blinds a message $M$ with blinding factor $b$ raise to the public key of the signer $e$ as $ b^e \cdot M $

(2) the signer will blindly sign the value by raising it to its private key $d$, as $ \sigma'^d = b \cdot M^d $

(3) the user will compute the signature $\sigma$ by multiplying $\sigma'$ by $b^{-1}$ as $\sigma = M^d$.

To forge a valid signature without needing the signer, you can start by an inverse process i.e. create a garbage message and signature pair $<\sigma=M,message=M^e>$.

This will work because when the verifier wants to check the validity of the message, signature pair it will raise the signature $\sigma$ to the public exponent $e$ and it will match. The down point for this is that the adversary will have rubbish message.


Secure Design and CRL? I was at my College Security Lesson, the professor said that Certificate Revocation Lists (CRLs) violate some of the Secure Design principles.
Secure Design Principles:

Fail-Safe Defaults
Economy of Mechanism
Complete Mediation
Open Design
Separation of Privilege
Least Common Mechanism
Psychological Acceptability

I can't really face this thing!

Which Secure Design principles are violated with the use of CRLs? Why?

OK, let's go over them:

Fail-Safe Defaults: this is the most important one, as a CRL doesn't provide on-line information and may not be available or out-of-date;
Economy of Mechanism: a CRL may contain information about many certificates, so the mechanism isn't as economic as it could be;
Complete Mediation: CRL's are public info while complete mediation is about access control and therefore this rule is not applicable;
Open Design: well, CRL's are an open standard as well - as part of X.509 and the derived RFCs, so it complies;
Separation of Privilege: privilege separation is not on topic here, both CRL's and OCSP's are generally performed by the same entity;
Least Common Mechanism: possibly the ASN.1 parser is shared with the X.509 certificate, but if the ASN.1 parser of the certificate is broken then you're already in trouble, I don't see how it applies here;
Psychological Acceptability: I guess nobody complains if certificate is refused because of a CRL and certainly nobody complains if it isn't, so this isn't really applicable.

Note that OCSP - the online certificate status protocol - does provide a positive way of knowing if a certificate is valid at that time or not. However, you still face the same issue if the OCSP server cannot be reached. Generally the certificate should not be accepted, but this is often configurable. Besides that, OCSP requires a higher availability of the service.

I'd hazard that the private key could be known to be exposed while the CRL is still valid is the biggest issue; without an online protocol it certainly doesn't comply fully with Fail-Safe Defaults.

However, your professor should not leave you guessing; ask your professor what was meant!


Is having AES tables on a distinct physical page enough to avoid cache timing attacks? Reading about typical cache timing attacks, they seem to be based on intentional eviction of cache lines and timing how long an operation takes.  It seems as if those attacks rely upon these tables being hardcoded constants in read-only sections of an executable, and are therefore subject to sharing memory pages.

If you ensure that your AES tables are on physical pages that are private to your process, is that enough to thwart timing-based attacks?  In this situation, an attacker running as a normal-privileged process on the same machine would not be able to perform such tricks as clflushing the cache lines containing the table.

Note that this technique also requires that the contents of the pages are also unique, not just private: some operating systems might notice memory pages with identical contents and coalesce them to a single physical page as copy-on-write.

No

You are misunderstanding how such attacks work. It's not that your page gets shared to some attacker process. Attacker might not even be present on your computer, only measuring time over internet.
Such attacks only depend on fact that if you access index 5, then every next access to index 5 will be faster. It doesn't require any method to remove data from cache (it will go away on it's own), but those can make attack faster.

For example here is attack that only used a server that included a cycle-exact time. No attacker program was present on victim machine.

As a side note: When process is attacker running as a normal-privileged process, it has access to all other normal-privileged processes in many OSes (for example Windows), so attacker can simply read key.


How exactly is an enigma simulation software supposed to encrypt alphabets? EDIT: The model I'm trying to make is "Enigma 1". I learned initially about it from a book called "Code Book" and then looked at it in detail from its wikipedia page. The rotor wiring and other details from https://en.wikipedia.org/wiki/Enigma_rotor_details

I am trying to make an enigma machine simulating software. I know how the machine works but am having trouble trying to understand what my code's logic should be BEFORE the alphabets get to the reflectors.

Suppose 1, 2 and 3 represent each rotor's settings in an enigma machine (they're what I got from wikipedia):

  abcdefghijklmnopQrstuvwxyz
1:ekmflgdqvzntowyhxuspaibrcj

  abcdEfghijklmnopqrstuvwxyz
2:ajdksiruxblhwtmcqgznpyfvoe

  abcdefghijklmnopqrstuVwxyz
3:bdfhjlcprtxvznyeiwgakmusqo

And suppose the message is "A". Here's what I think should happen: From the first rotor, the message could have become "E" but because the rotors spin by one unit before the encryption, it is encrypted to the next letter in the setting: "K".
Now to find what happens in the second rotor, we need to see the 11th letter in the setting (or the letter below K) which is "L".
Similarly for the final rotor, we see the 12th letter (below "L") which is "V" and that from my understanding should be what is transferred to the reflector and then back.

Though my software is complete with ring settings, plugboard and all the other stuff and it can decrypt it's own encrypted messages the way it is supposed to, the ciphertext is never the same as what online enigma simulators produce for the same settings, nor can it decrypt original messages even if I know all the settings. If you go here:
http://people.physik.hu-berlin.de/~palloks/js/enigma/enigma-u_v20_en.html
click "show monitor" button and type "a" you will see that before it reaches the reflector, it is translated as "H". So clearly I'm doing something wrong.

Can somebody please help me out?

I guess you already figured it out but my guess is that you forgot to move the first rotor 1 step before starting the encryption. That also impacts what letter it arrives to on next rotor and so on.

The complete path is

KBD-A>SB>A - A>ETW>A - B>(1)R3>K - J>(2)R2>B - B>(3)R1>D - D>UKW>H
  - H>(3)R1>D - D>(2)R2>C - D>(1)R3>G - F>ETW>F - F>SB>F-light

Keyboard A arrives to plugboard (Steckerbrett) as A, leaves the plugboard as A, arrives to Entry wheel as A, leaves as A, arrives to the first rotor at level B, gets rewired to K and so on.
Typing 3 more "A" gives

 A>SB>A - A>ETW>A - C>(1)R3>M - K>(2)R2>L - L>(3)R1>V - V>UKW>W
       - W>(3)R1>R - R>(2)R2>G - I>(1)R3>V - T>ETW>T - T>SB>T  :T

 A>SB>A - A>ETW>A - D>(1)R3>F - C>(2)R2>D - D>(3)R1>H - H>UKW>D
    - D>(3)R1>B - B>(2)R2>J - M>(1)R3>C - Z>ETW>Z - Z>SB>Z  :Z

 A>SB>A - A>ETW>A - E>(1)R3>L - H>(2)R2>U - U>(3)R1>K - K>UKW>N
    - N>(3)R1>N - N>(2)R2>T - X>(1)R3>Q - M>ETW>M - M>SB>M  :M


Keyed-hash of a lot of small numbers Let's say I have a list of several million numbers, with only 6-9 digits of secret information per number (this means that an attacker might efficiently guess the other digits). I have to store the list in an unreadable format and when given a new number I want to efficiently know if I have the number in my list or not.

For this purpose I store the HMAC – SHA 256 of my numbers, using the same secret key to generate all the hashes. When given a new number I use the secret key to compute its HMAC - SHA 256 and perform a lookup in my list.

I am also storing the same numbers encrypted with another key in AES CBC mode, but this field is not useful for searching because of the random IVs.

Is this secure, cryptographically speaking? Will it prevent attacks to "open" the hashes, assuming the secret key remains unknown to an attacker?

As long as the key is secret, your list of MACs is safe and the numbers are not guessable.

You probably can truncate your MACs to 80 bits in order to save space, as collisions are highly unlikely for $2^{23}$ entries or so.

If your numbers do not repeat and fit into 128 bits, the simple Electronic Codebook (ECB) mode with AES should also do a good job, you just store the ciphertexts encrypted on the same key.


Strong One-Way Function In the book "Foundations of cryptography-Oded Goldreich-Page 33", if we use the deterministic polynomial-time algorithm instead of the probabilistic polynomial-time algorithm for case 2 (Hard to invert), what would be the situation?

Suppose we live in a work where $\mathsf{P}\neq\mathsf{BPP}$ - that is, there exists problems which can be solved in randomized polynomial time, but not by any deterministic polynomial time algorithm. In such a word, if we define a OWF as a function which is hard to invert for deterministic polytime adversaries, we might in fact have no real guarantee for its security: in the real world, it's not so hard to generate random bits (say, using some appropriate quantum device). Hence, there could exist an attack which works well in the real world, using a source of random bits, even though the OWF might be secure against all deterministic adversaries. Hence, such a definition would not capture correctly the class of functions which allow for secure cryptographic applications.

Note, however, that it is widely believed that $\mathsf{P} = \mathsf{BPP}$. Indeed, this follows from some worst-case circuit lower bounds (or equivalently, the existence of some strong form of pseudorandom genarator): if there exists problems in $\mathsf{DTIME}(2^{O(n)})$ which have circuit complexity $2^{\Omega(n)}$, then $\mathsf{P} = \mathsf{BPP}$.


Simple explanation of Miller's algorithm Could someone explain to me in few lines (even one sentence) what Miller's algorithm computes?

Without talking about divisors and all the other concepts, I would like to be able to explain it to someone who doesn't necessarily know elliptic curve cryptography in details but understands the basics because it's a really abstract concept.

Like what is the value returned by the Miller's function and why use this function ?

Miller's algorithm maps two points in a elliptic curve into a element of a finite field. So, if you have a point $P$ and a point $Q$, then Miller's algorithm (which we'll denote $e$) will compute some value $r \leftarrow e(P, Q)$, where $r$ is a finite field element.

Recall that points can be added (e.g. $T \leftarrow P + Q$) and multiplied by a integer (e.g. $T \leftarrow kP$, which is just repeated addition), while finite field elements can be multiplied (e.g. $t \leftarrow pq$) and raised to the power of an integer (e.g. $t \leftarrow p^k$, which is just repeated multiplication).

The crucial property of Miller's algorithm is bilinearity. Assume that you have points $P$ and $Q$ and integers $a$ and $b$, and compute the points $R \leftarrow aP$ and $S \leftarrow bQ$. Then, if you compute Miller's algorithm for $P$ and $Q$:

$x \leftarrow e(P, Q)$

and for $R$ and $S$:

$y \leftarrow e(R, S) = e(aP, bQ)$,

then these values will be related with:

$y = x^{ab}$.

In other words, bilinearity means that:

$e(aP, bQ) = e(P,Q)^{ab}$.

The bilinearity property allows the construction of cryptographic protocols which were not possible before or too complicated: identity-based cryptography, short signatures, non-interactive key agreement, and so on.


Why is private key chosen to be less than chosen prime in diffie-hellman? since the public key is calculated as Y=(alpha^private-key)mod(chosen prime) and alpha is a primitive root of prime, when Y becomes public then private key can be calculated easily right? since there is a unique private key less than chosen prime that will satisfy the equation. I think I'm missing something here. Please help.

since the public key is calculated as Y=(alpha^private-key)mod(chosen prime) and alpha is a primitive root of prime, when Y becomes public then private key can be calculated easily right?

One certainly hopes that it cannot be calculated easily, at least, for the 'chosen prime' that we pick.

since there is a unique private key less than chosen prime that will satisfy the equation.

There's a difference between showing that the equation has a solution, and demonstrating that solution.  That the equation has a solution can be shown by relatively simple number theory; as for finding that solution, the best known algorithm [1] for solving it for unstructured [2] values of $p$ takes superpolynomial time, that is, it slows down (as larger values of $p$ are considered) faster than any polynomial.  The largest unstructured $p$ for which there is a published solved random discrete log problem is circa 768 bits long; we currently use values of $p$ that are at least 2048 bits long (and sometimes longer).
BTW: we generally don't use values of $\alpha$ that is a primitive root; we prefer values that have a large prime order, as that leaks less data about the private value we picked.

[1]: on a conventional computer (such as what you are using to read this web site).  There is a known algorithm that runs on a Quantum Computer which runs in polynomial time; however we currently don't have a Quantum Computer that's large enough and reliable enough to implement that algorithm).
[2]: it turns out to be an easily problem if $p-1$ doesn't have any large prime factors; we deliberately select the $p$ values we use in practice so that $p-1$ does have a large prime factor.


SNARK-friendly one-way compression functions I'm looking for a one-way compression function that is secure and efficient within a zk-SNARK circuit. The motivation behind this comes from these considerations:

SHA256-compression is highly inefficient for SNARKs
The Pedersen hash function is efficient, but has an upper input limit of 32 bytes and outputs 32 bytes
A Merkle-tree implementation requires a hash function that accepts an input 64 bytes (the 32-byte outputs of two hashes).

Hence I'm looking for a way to securely and efficiently combine two 32-byte values into one 32-byte value.

I'm considering the MiMC hash function for this purpose but it seems like overkill for this purpose; I am already hashing data using Pedersen. Perhaps MiMC with fewer rounds would work well, but perhaps there's a better way to do it.

If you just need one-wayness (and not e.g. collision-resistance), want a compression function, and have 64 bytes of inputs, then there is a chance that you are exactly in the regime where Goldreich's one-way function, with proper choices of parameters, is unbeatable.

Concretely:

Pick once for all (and store) 256 uniformly random size-5 subsets of $[1,512]$. Denote them $(S_i)_{i \leq 256}$.
Define the following compression function $f$: on input $x \in \{0,1\}^{512}$, compute each of the 256 bits $y_i$ of the output as $P(x[S_i])$, where $x[S_i]$ denotes the subset of five bits of $x$ indexed by $S_i$, and $P$ denotes the predicate:

$P : (x_1,x_2,x_3,x_4,x_5) \rightarrow x_1 \oplus x_2 \oplus x_3 \oplus x_4\cdot x_5$.

Goldreich's function was thoroughly studied in the last 20 years (see the introduction of my paper for an overview). It's security is still far from perfectly understood, but essentially, the security decreases strongly when you look for a very long output. When you actually want a compression function and have a 512-bit input, I believe it should guarantee a clearly sufficient level of security.

As a bonus, observe that this is a completely parallelizable function: all output bits can be computed in parallel.

(of course, there are several other alternatives with low number of multiplications, or small circuit depth, but I think the above looks like a very good choice).


Randomizing before Shamir secret sharing? As I understand, the security of key-sharing depends on the cleartext actually being random.

If I split a secret which contains things like ASCII or even fixed strings (think -----BEGIN PGP PRIVATE KEY-----) what kind of preprocessing is recommended?

My current thinking is either one time Pad:

$ \text{Shamir}_{(N,M)} \left(\left( \text{secret} \otimes \text{random}
\right),\text{random} \right) \rightarrow M \text{ shares} , N \text{ required}$

or multiple rounds of AES:

$ \text{Shamir}_{(N,M)} \left(\text{AES}_{key}\left(\text{secret}
\right)^{rounds},\text{key} ,\text{rounds}\right)\rightarrow M \text{ shares} , N \text{ required}$

As I understand, the security of key-sharing depends on the cleartext
  actually being random.

Actually not, the premise of the Shamir Secret Sharing (SSS) scheme is that it is information-theoretically secure.

That means if you require $N$ shares for reconstruction and an attacker has $<N$ shares, the following equation holds:
$$\Pr[M=m\mid C=c]=\Pr[M=m]$$

Which basically says that given the ciphertext you know as much about the plaintext as you know without having the ciphertext.

Or, put differently, as tylo said in the comments:

  He can guess, but he can't check if his guess was right.

As for why this holds (as you may ask yourself now): Notice that SSS basically encodes your secret as the point $(0,s)$ and that the shares are points $(x,f(x)), x\neq 0$ of a (nearly-random) polynomial of degree $N-1$ over some field (usually $\mathbb F_p^*$). Now imagine as an example you're given 2 points of a degree-2 polynomial (which would be N-1 shares). For every possible $s$, you can now find a third point such that $(0,s)$ is on the polynomial. Put otherwise: There's no additional constraining condition that would help you narrow specific plaintexts down as more likely.


Why is there an enormous difference between SAT solvers? SAT solvers are very important in algebraic attacks, for example walksat and minisat.

However, when solving the benchmark problems available here there is an enormous performance difference between the two - Walksat is much faster than minisat for these problems. Why is this?

This implementation of walksat appears to have some performance improvements - is there any reason it wasn't included in the international SAT Competitions?

SAT solvers don't have a single approach -- not every approach works equally well for every problem. A SAT solver that performs well on a given problem will not necessarily work well in general.

Typically SAT solvers employ a whole bag of tricks -- deciding what heuristic to employ is one of the big differences between solvers. Different heuristics work well for different types of problems and a solver must identify traits of the problem at hand to decide which heuristic to use (unless the user specifies which heuristic to use, which one might, if one knows what to do, or for experimentation purposes).

As to why a given solver wasn't entered in the international SAT competition, you'd have to ask the creator of the solver! I'm pretty sure they could submit it if they wanted to...


Why is the salt used only once in PBKDF2, while the password is used often? The purpose of PBKDF2 is to create a derived key (DK) from a master password (PW) and a salt, often using a function like HMAC-SHA256.  I have read that the salt should be as random as possible.  But if that's the case, why does it play such a minor role?

I'll let the equations speak for themselves, starting with HMAC-SHA256:

$$\def\op{\operatorname}\def\0#1#2#3{\text{0×#2#3}}
\op{HMAC-SHA256}( PW, m ) = \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ m ) ) $$
where
$$\begin{align*}
K &= \begin{cases}
    PW &\textrm{if } \op{bytes}( PW ) = 64 \newline
   \op{SHA256}( PW ) ∥ [\0x00]_{32} &\textrm{if } \op{bytes}( PW ) > 64 \quad \textrm{ (32 zero bytes)} \newline
 PW ∥ [\0x00]_{64-\op{bytes}(PW)} & \textrm{if } \op{bytes}( PW ) < 64
\end{cases} \newline
K_i &= K ⊕ [\0x36]_{64} \newline
K_o &= K ⊕ [\0x5c]_{64} \newline
\end{align*}$$

Now PBKDF2:

$$
\begin{align*}
DK &= T_1 ∥ T_2 ∥ ... ∥ T_{\op{len}(DK)/\op{len}(T_i)} \newline
T_i &= U_1^i ⊕ U_2^i ⊕ ... ⊕ U^i_{\text{iterations}} \newline
U^i_1 &= \op{HMAC-SHA256}( PW, \op{salt} ∥ \op{INT32}( i ) ) \newline
U^i_n &= \op{HMAC-SHA256}( PW, U^i_{n-1} )
\end{align*}
$$

But watch what happens if the two are combined:

$$\begin{align*}
 U^i_1 &= \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ \op{salt} ∥ \op{INT32}( i ) ) ) \newline
U^i_2 &= \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ \op{salt} ∥ \op{INT32}( i ) ) ) ) ) \newline
& \dots
\end{align*}$$

Or in pseudocode:

$$\begin{align*}
&T[i] = 0 \newline
&U = \op{salt} ∥ \op{INT32}(i) \newline
&\text{for } n = 1 \text{ to }c: \newline
&\qquad U = \op{SHA256}( K_i ∥ U ) \newline
&\qquad U = \op{SHA256}( K_o ∥ U ) \newline
&\qquad T[i] = T[i] ⊕ U \newline
&\text{next }n \newline
\end{align*}$$

So the salt is used only once per output block, while the master password is used twice per iteration (in the forms $K_o$ and $K_i$).  I understand that the avalanche effect means a slight change in the initial hash input will have a significant impact on the hash output, but wouldn't it make sense to introduce as much entropy into the final result as possible?

Summary: I don't know of any good reason why it has to be this way. In practice, I don't think it is necessary to inject the password into every iteration.  As far as I know, I think the construction would still be secure (in practice) if you used the salt and password only in the input to the first iteration, and then just repeatedly hashed the result many times without feeding in the password any further.

So why does PBKDF2 do it, if it is not strictly necessary for security?  I don't know.  I can only speculate -- and you should take my speculation with a large grain of salt.  That said, my speculation is that, by using the key in every iteration, you can get some slightly better provable-security results.

Technical speculation: it has to do with the security proof.  In particular, with PBKDF2, it is possible to prove a statement along the lines of: if HMAC-SHA256 is a secure PRF, and if the password is a full-entropy full-strength crypto key, then PBKDF2(password, salt) is a secure cryptographic key.  No such statement would available if every iteration after the first used a bare hash instead of a HMAC PRF; you'd need to make stronger assumptions, such as work in the random oracle model (i.e., assume that the hash is perfect in every regard).

That said, the difference in provable security feels rather negligible to me.  The security claim that you can prove about PBKDF2 (without the random oracle model) is not very exciting.  PBKDF2 is primarily used to derive keys from a memorable password that is not full-entropy, and that situation is not covered by the security proof above.  So, as far as I can see, I don't know of any compelling reason why PBKDF2 was designed to inject the password into every iteration of the algorithm.

Standard disclaimer: don't roll your own. Please don't take this post as a justification for modifying PBKDF2 and using your modified version of PBKDF2.  That would be a pretty risky thing to do.  Even if we can't think of any strong reason why PBKDF2 had to be designed the way it did, it's still safer to use the standard primitive.  PBKDF2 has been well-vetted, and who knows, maybe there's some problem with the variant that hasn't occurred to me.


Are poly1305 authenticators distinguishable from random data? Assume Alice authenticates a message $M$ with nonce $N$ and secret key $K$, creating authenticator $A$. She then sends $A$ across the network.

The Poly1305 paper does not seem to specify whether it is possible for an adversary, whom has seen $A$, to determine whether $A$ is just random bytes or has characteristics of an output from poly1305.

For someone interested in deniability, this is an important distinction. Are poly1305 authenticators distinguishable from random data?

No, they are not distinguishable from random.

The Poly1305-AES authenticator is defined as:

$$
(((c_1 r^q + c_2 r^{q−1} + ... + c_q r^1 ) \bmod {(2^{130} - 5)}) + \operatorname{AES}_k (N)) \bmod 2^{128}
$$

Since it is the sum of an AES output and some other number modulo $2^{128}$, it is PRF if:

the AES output is PRF and
the two numbers are independent.

AES output looks like PRF as long as you see less than ~$2^{64}$ of them and $k$ and $r$ are required to be independent (since they are chosen from a uniform distribution), so the authenticators are indistinguishable from random at least as long as you see significantly fewer than $2^{64}$ of them.


how do i implement zero knowledge proof? I am new to this concept of zero knewledge proofs, from what I understand it is not a mathematical general equation like RSA or ECC cryptography has, but its a methodology that varies from problem to problem.

What I want to do is to let a prover prove that his public key belongs and exists in a known public bulletin board that contains a list of public ECC keys without revealing the public key so it should be encrypted (the public key should be encrypted for privacy reasons).

Theoretically speaking it's rather easy.

You simply have the key owner (the prover) perform a proof that they have the private exponent for at least one of the public keys on the list. This is a standard OR-proof which composes multiple (Sigma) Zero-Knowledge proofs. As you're using standard elliptic curve crypto the public keys will be of the form $P_i=[x_i]G$ for a private key $x_i$ and the public key $P_i$ and some curve-defined generator $G$, this allows you do use a standard Schnorr-proof.

Prover (knowing $x_i, P_1,\ldots, P_N$):

Randomly choose $r\stackrel{\$}{\gets}\mathbb Z_q$ that is an integer in $[0,q)$.
Compute $a_i=[r]G$
Choose random $c_1,\ldots,c_{i-1},c_{i+1},\ldots,c_N\stackrel{\$}{\gets}\{0,1\}^h$ for $h$ being the output length in bits of your favourite hash function, e.g. SHA-256.
Randomly choose $z_1,\ldots,z_{i-1},z_{i+1},\ldots,z_N\stackrel{\$}{\gets}\mathbb Z_q$ and set $a_j=[z_j]G-[c_j]P_j$ for all $j\neq i$.
Compute your favourite hash function $c=H(a_1\|\ldots\|a_N)$ or alternatively receive a random $h$-bit string from an interactive verifier after sending them the $a_1,\ldots,a_N$ or if you have some context $m$ to the proof, append it at the end of the hash input.
Compute $c_i=c\oplus c_1\oplus\ldots\oplus c_{i-1}\oplus c_{i+1}\oplus\ldots\oplus c_N$
Compute $z_i=r+x_i\cdot c_i\bmod q$
Output (c_1,\ldots,c_N,z_1,\ldots,z_N) as the proof along with $m$ if any. For the interactive case outputting the $z$s suffices.

Verifier (knowing $P_1,\ldots,P_N$ and receiving $(c_1,\ldots,c_N,z_1,\ldots,z_N)$ as well as the optional $m$):

In the interactive case: Output a random string $c$ of length $h$-bit after getting the $a$s, then receive the proof.
Compute all the $a$s: $a_i=[z_i]G-[c_i]P$
In the interactive case: Check that $c_1\oplus\ldots\oplus c_N=c$ and that the $a$s computed in step 2 match those received before step 1.
In the non-interactive case: Check that $c_1\oplus\ldots\oplus c_N=H(a_1\|\ldots\|a_N)$ or with the context appended as specified.
If no check failed so far, accept the proof, otherwise reject it.

Of course the issue with the above protocol is that the proof scales linearly with the number of public keys on the board, but you'd need more sophisticated approaches to solve that (e.g. Ring Signatures).


Matsui's Linear attack on DES P box I'm trying to understand Matsui's linear attack on DES and I have something I don't understand in his paper. In his paper he say that:

$NS_{5}(16,15)=12$ (which is OK)

and from that he say that:

$X[15]\bigoplus F_5(X,K)[7,18,24,29]=K[22]$

My problem here are the indices 7,18,24,29 - where did they come from?
They are supposed to be the output bits of S5 after the P box but those bits are 17, 32, 24, 26 if I take the P box from wikipedia. Why is that true?

We need to get back to Matsui's notations.

X is represented as X[31]....  X[0]

K is represented as K[47]......K[0]

In X[15] ⨁ F5(X,K)[7,18,24,29] = K[22]

X[15] is actually the round input before expansion E and is therefore the 4th bit of SBOX 5 with input bits of S5 being x[5]x[4]x[3]x[2]x[1]x[0]. X[15] = x[4] in practise and the key bit is the 23rd from right to left, hence K[22] because the first one is K[0].

Then F5(X,K) = P(S5(X, K)), for which we sum up the 4 output bits. The bits straight out of S5 are Y[15], Y[14], Y[13] and Y[12], with Y = Y[31]......Y[0] using Matsui's notation, Y is mine.

If we apply P to Y,  P(Y[15]Y[14]Y[13]Y[12]) is the permuted output of S5 (that would be P(Y[17]Y[18]Y[19]Y[20]) in a "normal DES" representation from left to right) and becomes Z[24]Z[18]Z[7]Z[29] before expansion for the next round.

Hence the result:
X[15] ⨁ Z[24] ⨁ Z[18] ⨁ Z[7] ⨁ Z[29] = K[22] or

X[15] ⨁ Z[7] ⨁ Z[18] ⨁ Z[24] ⨁ Z[29] = K[22] as presented by Matsui.

Note 1: X is the input of round R before expansion, Z is the input of round R+1 before expansion

Note 2: it looks like Matsui used the processor's bit order as opposed to standard DES notations

Kiss


Are there cryptographic hash functions which do not have any collisions? I've been studying digital signatures and hash functions recently, and I was wondering: Do hash functions exist which will never produce collisions?

This is impossible for any generally useful hash: a hash must map all inputs to a fixed-length output, but you normally want to be able to take variable (and fairly long) inputs. The problem is that there are more inputs than outputs: you normally want to be able to hash any string up to a fairly big length, but the hash itself should not be too long, and there are more long strings than short ones.


IND-CPA secure RSA padding with a partial homomorphic property A while ago, I asked for an IND-CCA1 secure padding for RSA that still allows for the multiplicative homomorphic property of RSA and got no answers (yet).

Now I've seen fgrieu's answer about standard RSA being deterministic and (only?) this weak version having the homomorphism. Not this reminded me again and made me formulate this (weaker) question out of curiosity:

Is there an RSA padding such that the padded scheme is IND-CPA secure and exhibits a partial homomorphic property?

Here is a padding scheme for RSA that I crafted for the question. It allows encryption of strictly positive integers up to some moderate bound $b$, and such that the (ordinary) product of the plaintexts can be found from the product of the ciphertexts modulo the public modulus $N$ (with knowledge of the private key, by the method's normal decryption and unpadding method).

Plaintext $x$ with $1\le x\le b<N^{1/8}$ is randomly padded as $y=x\,r$, where random padding multiplier $r$ is a randomly seeded prime with $N^{1/8}<r<N^{3/8}$. Raw RSA encryption is then applied to $y$.

After raw RSA decryption, unpadding pulls the factors of $y$ at most $b$, and outputs their product $x$. It is possible to recognize a ciphertext obtained by using the homomorphic property from one that is not, by testing if $y/x$ is composite or not.

This has no discernible practical interest, but seems plausibly IND-CPA secure, and actually workable: padding can be made more efficient than RSA key generation; Pollard's Rho is enough for decryption for small $b$, and ECM will make $b=2^{128}$ feasible.

Variants are possible allowing decryption of the product of up to $h>2$ terms, by adjusting $b$ and the bounds for $r$. We want that $r_\text{max}<N^{1/h}/b$ and $r_\text{min}>b$. If we go that route, we also need to check that the public exponent $e$ is high enough that it remains overwhelmingly likely that $e\log_2r\gg\log_2N$, in order to prevent an $e^\text{th}$ root attack; and that there remains ample entropy in the choice of $r$ (well over twice as many bits as the security level) in order to avoid some meet-in-the-middle attacks.

We also have the option to widen the choice of the padding multiplier $r$, allowing any $r$ such that all its prime factors are above the plaintext bound $b$. That allows selection of $r$ in ways speeding-up (at least on average) the factorization job for un-padding. This is especially desirable for ciphertext obtained by the homorphic property, where it becomes compute-intensive to ensure that all unknown factors of $y$ are above $b$. We can choose $r=\prod s_i$ as the product of random primes $s_i>b$ :

with $s_i$ bounded by some moderate $s_\text{max}$, which will make Pollard's Rho efficient;
or with $s_i=1+\prod t_j$ for random primes $t_j$ bounded by some even more moderate $t_\text{max}$, which will make Pollard's $p-1$ efficient.


What is the most light-weight symmetric cipher thats still usefull? I need a very light encryption scheme which costs almost no performance during encryption (while decryption may be slow).

I found 5 algorithms: RC4, DES, LED, PRESENT, and Piccolo.

But how do I pick one that's faster than AES on my platform?

Salsa/ChaCha and the other eSTREAM winners are likely to be the "fastest but still secure" options today.

Don't forget authentication of course. Reduced-round ChaCha/Poly1305 is likely to be the fastest software-only option, due to tuned implementations in the libsodium and NaCl libraries.

UPDATED: The following slide deck has good info on state of the art lightweight block ciphers vs. legacy (along with source code links). Considers code size, RAM, and cycles/byte metrics for many algorthims).

Stream ciphers such as those from eSTREAM may be a better option than block ciphers. Even choosing RC4 and hardening it by dropping the first 512 bytes may be a good solution; code size doesn't get much smaller than RC4.


How to be able to change the password to access data encrypted with AES-GCM, without reencrypting? Let's say you need to encrypt plaintext which is 1 TB big.
You have a password pwd. This very classical AES-GCM process is applied (pseudo code):
salt = 16 random bytes
key = PBKDF2(pwd, salt, count=1000*1000)  # key derivation function
nonce = 16 random bytes
ciphertext, tag = AES_GCM_cipher(key, nonce).encrypt(plaintext)    # by blocks in reality
save to disk:
     salt | nonce | ciphertext | tag

Now if I suspect pwd to be compromised, and I want to change it to pwd_new, I have to restart the whole encryption process which might be long for 1 TB of data.
Question: which simple encryption scheme can I use, still using AES-GCM for the actual data, such that I can change the password without having to reencrypt/rewrite all the data?
(There are implementations of this for example in Microsoft BitLocker disk encryption, etc.)

This is case for the Fundamental theorem of software engineering which states:

"We can solve any problem by introducing an extra level of indirection."

In this case what is usually done is introducing an extra randomly drawn intermediate key (usually called "data encryption key, DEK").
You then encrypt the DEK with a key derived from your password (also sometimes called "key encryption key, KEK") and whenever you want to change the password you simply rederive the KEK, decrypt the DEK and derive the KEK under the new password to encrypt the DEK with (also preferably using a fresh salt).


When is public-key crypto used / when is symmetric crypto used? I read in the book "Cryptography & Network Security" that it has almost been universally accepted that public-key cryptography is restricted to only being used for key management (Does this mean sending symmetric keys securely using a public-key crypto system?) and signature applications.

Can someone explain me if these really are the only cases where we use public-key cryptography?
Also, does this mean that public-key cryptography can't be be used alone for sending messages and that for such an example we use both a public-key cryptosystem and a symmetric cryptosystem for sending for example an e-mail?
Furthermore, can someone give me some examples of where we use public-key cryptography and where we use symmetric cryptography?

I know it is a lot of questions, but i have done a lot of searches online and in books and cannot seem to find the exact answer to my question.

One of the biggest drawback of the currently known public key schemes are the performances: it is slow. For instance, when using RSA, nowadays, one has to work with numbers in the range $\left[2^{2047},2^{4096}\right]$, which are really huge.

You've effectively understood correctly: generally, one encrypts data using a symmetric algorithm, which is fast, using a random "data encryption key" and then encrypts this key using public key cryptography.

This is the case for PGP, for instance. So when you are sending a mail encrypted with PGP, most of the time, the actual data is encrypted using AES, while only the AES key is encrypted using RSA.
This is generally called a "hybrid cryptosystem".

Symmetric encryption is effectively used to encrypt data, most of the time. This is true for all current schemes and protocols: TLS, PGP, etc. all rely on the fast symmetric encryption for the data.
Asymmetric encryption (also known as public-key) is generally only used to encrypt small packets, like a key.

Another use of public-key cryptography is for signatures, but when you are signing a message, what you'll sign is actually the hash of the message, so you benefit from the speed of the hash function and the slow public-key operation are only performed on a hash.
This also means that public key crypto is at the heart of the certificates everybody uses on the internet nowadays, since those are a special case of public key signatures in order to build a "chain of trust".

Finally, you mentioned the key management, and public-key cryptography is also used there to perform key exchanges, in order to establish a common key between two parties over an untrusted channel, given that they both have each other public key. That common key is then generally used to encrypt data over that same channel with a symmetric algorithm.


Can you help me understand ECC Cryptography and it's algorithm? I want to know the basic understanding of ECC algorithm for cryptography. But I am not aware of the algorithm. Can anyone provide me with a basic explanation of the algorithm?

One can go on and on if to define and describe Elliptic Curve. I will rather suggest for you to get hold of a decent book and read for yourself. If you an issue with understanding any algorithm or basic of Elliptic Curve, I will be more than happy to help you there. For starter, you can always look at Silverman's book titled The Arithmetic of Elliptic curves. Else just go to Galbraith's webpage on Elliptic Curve Cryptography. There are bunch of nice books listed.


Efficient calculation of point coordinates with elliptic curves over binary field I'm trying to find an efficient algorithm to calculate the $y$ coordinate of a an elliptic curve point given its $x$ coordinate, for elliptic curves over fields of the form $2^m$ with polynomial representation of the field elements.

I had the exact same problem with elliptic curves over prime fields, but it is very simple to solve:

$y^2 = x^2 + ax +b \implies y = \sqrt{x^2 +ax +b}$

With this equation, all we got to do is to calculate the value of the second member, check if the value is a quadratic residue modulo the prime number (using Euler's criterion) then calculate the root, if it exists, using Tonelli-Shanks algorithm.

For binary fields the equation is

$y^2 +xy = x^3 +ax^2 +b$

Fixing the value of $x$, the equation can be reduced to something like

$y^2 +uy  +v = 0$

It is a simple quadratic equation, but I can not solve it with the polynomial arithmetic, since we have $y = \frac{-b \pm\sqrt{b^2 - 4ac}}{2a}$  and multiplying by an even number using this arithmetic results in $0$. Even worst, it would be necessary to divide by the scalar $2$ to find the roots, and there is no such operation defined.

Of course there is brute force, to test all polynomials with degree less than the degree of the reduction polynomial, but it is impractical as soon the the degree gets to high.

I'm new here and I would appreciate some help.

First, break it into a simpler problem: Divide by $u^2$ to rewrite $y^2 + uy + v = 0$ as $$(y/u)^2 + y/u + v/u^2 = 0;$$ then solve for $y/u$, and multiply the result by $u$.

$% Evidently mathjax's \operatorname fails to kern properly, so
% \operatorname{Tr} has an awful gap between T and r.  Worse, the
% \operatorname command blindly substitutes \text{-} for - anywhere
% in its argument, so \operatorname{T\kern-.98pt r} fails.  (This
% kern assumes cmr10 (actually, lmroman10, on which latinmodern-math
% is based), where the true value is (1.5*23.5/36)pt, which is
% approximately .695pt.  No \mathchoice because mathjax doesn't do
% smaller designed font sizes; it just scales cmr10 to other point
% sizes.)
\def\Trname{T\kern-.695pt r}%
\DeclareMathOperator{\Tr}{\Trname}%
\DeclareMathOperator{\GF}{GF}%
% Fake \clap.  Real one is (modulo math mode conditionals):
% \def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\clap#1{\mkern-10mu#1\mkern-10mu}%
$How do you solve $t^2 + t + d = 0$ for $t$?  (Here $t = y/u$ and $d = v/u^2$.)  Suppose we are working in $\GF(2^m)$.  It is necessary that $$\Tr(d) := \sum_{i=0}^{m-1} d^{2^i} = d + d^2 + d^4 + d^8 + \dotsb + d^{2^{m - 1}} = 0,$$ where $\Tr(d)$ is the trace of $d$ over $\GF(2^m)$ as a field extension of $\GF(2)$, for if $\alpha$ is a root of $t^2 + t + d$ in $\GF(2^m)$, then $\Tr(d) = \Tr(\alpha^2 + \alpha) = \Tr(\alpha^2) + \Tr(\alpha) = \alpha^{2^m} + \alpha = 0$.  Now break this down into two cases.

$m$ is odd.  In this case, the half-trace

\begin{align*}
     H(d) := \sum_{i=0}^{\clap{(m - 1)/2}} d^{2^{2i}}
           = d + d^4 + d^{16} + \dotsb + d^{2^{m - 3}} + d^{2^{m - 1}}
   \end{align*}

is related to the trace $\Tr(d)$ by

\begin{align*}
     H(d)^2
       &= \sum_{i=0}^{\clap{(m - 1)/2}} \bigl(d^{2^{2i}}\bigr)^2
        = \sum_{i=0}^{\clap{(m - 1)/2}} d^{2^{2i + 1}} \\
       &= d^2 + d^8 + d^{32} + \dotsb
          + d^{2^{m - 2}} + d^{2^m} \\
       &= d^2 + d^8 + d^{32} + \dotsb
          + d^{2^{m - 2}} + d \\
       &= \Tr(d) + H(d) + d,
   \end{align*}

since squaring is linear in $\GF(2^m)$.  If $t^2 + t + d$ has a root so that $\Tr(d) = 0$, then we have $H(d)^2 + H(d) + d = \Tr(d) = 0$; hence $H(d)$ is a root of $t^2 + t + d$.
$m$ is even.  This case is a pain, and therefore left as an exercise for the reader who is less lazy than I am.  (Hardly anyone ever uses elliptic curves over even-power binary extension fields in cryptography; usually the power is an odd prime.)


Is there any protocol for proving that a message was written at a certain time? Does there exist a way to cryptographically prove that a message was written at a certain time? I know that one can write messages in bitcoin transactions to that the message is preserved in the blockchain, which can be used to prove the message was written at that time, but I'm wondering if there is any protocol that exists specifically for the purpose of proving the time of a message.

In general, no.

You can prove a message was written no later than time T by hashing the message with a collision-resistant hash, and communicating the hash to some trusted third party that records it was aware of the hash at time T. The bitcoin blockchain can be used as a third party here. You don't need to put the whole message in the blockchain, just a hash.

You cannot prove a general message was written no earlier than time T. If there was an alleged way to prove that, you could just write a message earlier than time T, wait for time T, and perform the alleged proof, tricking any verifier.

If you can communicate back and forth with a verifier, you can prove you are writing the message during the communication, by hashing your message along with some random data provided by the verifier and passing the hash back to the verifier.


Why can't we give block ciphers larger keys? I have limited math's knowledge so sorry if this question sounds stupid.

I saw many people complaining about AES, Twofish and Serpent that these ciphers all could be crackable in the near future and even today with big datacenters.
But all these ciphers use max. 256 bit keys . And because there is no better way of finding the key then brute force the ciphers are equally strong.

Would it be possible to take these algorithms e.g AES and just change the key size from 256 to 512 or 1024? I mean the algorithm is well tested, you would just have to modify the key and block size.

I saw many people complainig about AES , twofish and serpent that these ciphers all could be crackable in the near future and even today with big datacenters .

This is a good example of why we should always ask for citations and explanations, rather then just accepting what people say at face value with no scrutiny. These claims are about as far from reality as possible.

  But all these ciphers use max. 256 bit keys . And because there is no better way of finding the key then bruteforce the ciphers are equally strong .

These 3 ciphers all have similar if not identical parameter configurations because they were all designed for the AES competition. It is true enough for practical purposes (but not exactly so) that all three are equally strong and that the only way you'll break them without side channel attacks is via brute force.

Which is to say that you won't break them, at all.

  Would it be possibel to take these algos e.g AES and just change the key size from 256 to 512 or 1024 ?

It is not possible to just increase the key size for an algorithm like AES; There are other aspects that are derived from the size of the key that you would have to take into account and modify as well. For instance, the AES key schedule (which is part of the AES block cipher) of AES-128 and AES-256 differs.

  I mean the algo is well tested , you would just have to modify the key and blocksize .

Ok, let's concede and say we construct such a thing, and also assume we don't somehow introduce additional points of failure while doing so: What problem have we solved by increasing the key/blocksize? It was already impossible to search. Perhaps this is a good question to ask those people that were complaining about how easy it is to break AES, twofish, and serpent...

Why can't we give block ciphers bigger keys

We can, we do not need to. You can always construct make an algorithm use more space and time. The goal is to use the least amount of resources possible to get the job done. Once you understand this, it will be clear why we do not use massive keys or hundreds of cipher rounds.


Authenticating a message with HMAC vs AES-CBC Given some string s I want to sign, are following methods are equivalent to produce message with signature, assuming it does not matter whether s is visible in message or not?

s + HMAC(s, secret_key)
AES_CBC(s + string_of_zeroes, secret_key)

And validation:

recalculate HMAC of first part of message and compare it to second one
decrypt message and verify that it ends with string_of_zeroes

If that is true, string_of_zeroes of what length should be taken to make them equivalent?

Given some string s I want to [integrity protect], are following methods are equivalent to produce message with signature, assuming it does not matter whether s is visible in message or not?

Absolutely not; with AES_CBC, if the attacker modifies one particular block of the ciphertext, then the decryption of the modified ciphertext will have two blocks modified (the one corresponding to the modified block, and one block after that).

Hence, if s is (at least) two blocks long, an attacker can freely modify the first block of the ciphertext; the decryption will still have the string of zeros still in place (as that wasn't modified), and so the attacker has succeeded in undetectably modifying the string.

If you need a MAC, use a MAC (alternatively, authenticated encryption).  And, make sure that a MAC is appropriate (that is, both the sender and the receiver share a secret key, and you don't mind if the receiver were able to generate valid-looking messages of his own).


DES Encryption: Looking for results for each round of encryption/decryption to debug code I've been searching for a few days in different forums trying to find an example of DES that gives the key/output values for all 16 layers. I found one that gives the encryption which helped me fix that part, but my decryption isn't working correctly. It's easier to debug if I know what I'm aiming for.
Is there someplace that has all the encryption/decryption round outputs that I can look at?
Should they be the same only backward? Decryption round 1 output = encryption round 16 output?
Thank you for any help you can give.

Should they be the same only backward? Decryption round 1 output = encryption round 16 output?

Yes, that is correct; the decryption subkeys are exactly the encryption subkeys in the opposite order.
I don't have the per-round test vectors you were asking for, but I can make this suggestion: if you have DES working in the encrypt direction, you can generate the test vector yourself; recording the state of the block after each round.  Then, when you attempt to decrypt the block, the per-round block state is supposed to traverse the same path backwards; for example, if the block state after encryption round 15 was X, then the block after after decryption round 1 should also be X.  If decryption isn't working, then somewhere during the cipher it went wrong; by looking at the per-round states, you should be able to narrow it down to a specific round.


How are "string-messages" converted to "number-messages"? Textbooks most of the time assume that a message, say "secret", is already represented in number format, say "8614" (just as an example!). But how exactly is this conversion achieved?

I imagine it to happen something like that:

"secret" is converted into the binary format, say "1001001" (names like ASCII or UTF-8 come to my mind, though I am not sure)
1001001 is somehow converted into a number, in above example "8614"

Could you please give me more details or some references so I can look it up?

Cryptographic schemes handle byte strings. To convert a string to a byte string, you need some encoding like ASCII (which can't handle every character) or UTF-8 (which can handle the entire Unicode).

Some specific schemes, like RSA, do need to interpret the byte string as a number. This process is defined in the scheme specification (e.g. for RSA, the PKCS#1 standard - see the OS2IP conversion function). In RSA, the byte string is read as a big endian number in base 256. For example, the byte string 0x01 0x02 is interpreted as the number 258 (256 * 1 + 2).


Equations modulo phi(n) Let $n$ be an RSA modulus and assume one has the two following equations

\begin{align}
y_1 = (x+a_1)^{-1} \pmod{\varphi(n)}\\
y_2 = (x+a_2)^{-1} \pmod{\varphi(n)}
\end{align}
with known $y_1$, $y_2$, $a_1$ and $a_2$, and where $\varphi$ is Euler's totient function.

Is it possible to solve the system and recover $x$?

From your equations, one can write:
\begin{eqnarray*}
x + a_1 &=& \frac{1}{y_1} \mod \phi(n) \\
x + a_2 &=& \frac{1}{y_2} \mod \phi(n) \\
\end{eqnarray*}
and thus:
\begin{eqnarray*}
a_1 - a_2 &=& \frac{1}{y_1} - \frac{1}{y_2} \mod \phi(n) \\
\end{eqnarray*}
which leads to:
\begin{eqnarray*}
(a_1 - a_2) y_1 y_2 - y_2 + y_1 &=& 0 \mod \phi(n) \\
\end{eqnarray*}

Therefore, one can compute $f = (a_1 - a_2) y_1 y_2 - y_2 + y_1$, and the equation above tells you that $f$ is a multiple of $\phi(n)$. At that point, you can take a random prime integer $e$ which is relatively prime to $f$ (take a random prime $e$, compute the GCD with $f$; if it is distinct from $1$, start again with a new random prime). This value $e$ will be "an RSA public exponent". You can then compute $d = e^{-1} \bmod f$, i.e. the corresponding "RSA private exponent".

Given a pair of public/private exponents $(d,e)$, one can factor the modulus $n$, using the method described here (a more formal reference is Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem). Once $n$ is factored, you then compute $phi(n)$, at which point you can recover $x = y_1^{-1} - a_1 \bmod \phi(n)$.


Any point to AES on password with hardcoded key? I'm inheriting a project that stores a used password in a config file, which is generated by the user giving their password in plain text, and the project giving back a key generated through .NET's Rfc2898DeriveBytes with a given salt on the aes encrypted cipher text (which the user then has to put in the config themselves). The password is decrypted and used when the project starts up for that user.

Since the key and salt are statically compiled into the project as strings, it seem kinda pointless to me, like basically its the same as storing a jibberish password in plain text, with added overhead, right?

Am I missing something here?

EDIT

After asking around about the code, the point is that we're giving this application to a different team to run under a network domain account, so we wanted to prevent them from having the password for the account the program is supposed to run under.

Obviously it would be easy to decrypt the password for any serious attacker, but it might help deter casual attackers. Instead of opening the config file in a text editor and finding the password they would have to decompile and decrypt it, or snoop the memory while it's running. It might also help to stop automated tools that may be searching the filesystem for documents containing things like "password=xxx".


multiplication of two points belong to elliptic curve I have a question about multiplication of two points belong to elliptic curve. I know every think about adding and scalar multiplication but not about multiplication of two points. Is there any method for this?

The reason that I need this is that in paper "Attributed-based encryption for fine-grained access control of encrypted data", we need choose group G and then a point g as the generator of this group. Then in setup algorithm, we should calculate g to the power of t1, while t1 is a number. So it means that we should multiply g into itself for t1 times. If we choose an elliptic field, how could we do this multiplication?

Thanks

I have a question about multiplication of two points belong to elliptic curve. I know every think about adding and scalar multiplication but not about multiplication of two points.

Actually, when the paper talks about 'multiplying' two points, it's talking about what we more conventionally call 'point addition'; and hence what they call "g to the power to t1", we conventionally call "multiply the point g by the integer t1, that is, g added to itself t1 times".

It's not clear why they decided to refer to the elliptic curve as a multiplicative group and not an additive one.  Their paper is from 2006; I had thought that, by that time, the additive convention was fairly prevalent.  One possibility is that they looked at the convention of $\mathbb{G}_2$.  The group $\mathbb{G}_2$ has an operation which is multiplication over a finite field (at least with any pairing operation you'd actually use), and hence is always written multiplicatively.  Perhaps they decided to write the operations in $\mathbb{G}_1$ (the elliptic curve group) to be consistent with it.


Is this the right way to implement ElGamal scheme over Elliptic Curves over prime field? I'm fairly new to Cryptography, especially elliptic curves in general. I learned to do Point Multiplication, Scalar Multiplication and also programmatically implemented them. But I was trying to do ElGamal scheme because I felt intrigued by the subtlety of it.
The problem that haunts me is this:
Suppose, I have a generator point G on an Elliptic Curve (say SECP256k1 or any curve) , an integer x, which is the private key of this scheme, and I generate the public key P= [x]G . Then, I encode the message to a single number (e) that will be surely less than p, the prime number of the field (256 bit).

ENCRYPTION : I generate a random number k, less than N, where N, is the order of the curve, and also: R = [k]P .
I also choose a point C = [k]G. Then I take the x coordinate of R, and do: (x_coordinate of R*e) modulo p -> this will be the cipher text.

DECRYPTION: I take the chosen point C, multiply it with x (private key) to recover the point R back, then I do :  (cipher_text*((x_coordinate of R)^(-1) modulo p))modulo p to recover e , the encoded message, which is then decoded back to plain text !

MY CONCERNS:
[1] Was that the right way to encode the message?
[2] If x_coordinate of R * e was smaller than 256 bits then modulo would output the same x_coordinate of R*e which can be easily factored on a computer, and x_coordinate of R could be recovered !

EDITS:
What can be the maximum size of x_coordinate of R * e when taking modulo p ? I understand that it should be less than p, but even when I take blocks of plain text such that Rx*e alone exceeds ( 485 bits)the bit size of p (256 bits) I'm able to recover the encoded message back ! I do not know the reason for this creepy behaviour!!! ? Sorry, I'm fairly new to the math of all this !!! BUT: If x_coordinate of R*e is of the order of 2000 bits I totally loose data !!! Infact I am getting it wrong if thats the case!
This is what gives me trouble:

/************************
     Code for illustration of
     my mathematical problem
******************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <gmpxx.h>

using namespace std;
mpz_class ModInverse(mpz_class a, mpz_class b)
{
    mpz_t inv;
    mpz_init(inv);
    mpz_invert(inv, a.get_mpz_t(), b.get_mpz_t());
    return mpz_class(inv);
}
int main()
{
      // Prime used by SECP256k1
      mpz_class p=mpz_class("115792089237316195423570985008687907853269984665640564039457584007908834671663");
      //Let this be some encoded message ...
      mpz_class msg=mpz_class("123115792089237316344566776544467896775567567584007908834671663758400790883");
      // Let this be the x coordinate of R
      mpz_class x=mpz_class("712164785702978780789493774073370493892893827485075314964804772812648384");

      cout<< "Encode Message :  "<< msg <<  endl;
      cout << "\nx coordinate of R * msg"<< msg*x << endl;
      cout << "Product bit length: " << mpz_class(msg*x).get_str(2).length()<< endl;
      // Bit length exceeds modulo bit length
      mpz_class cph=(msg*x)%p;
      cout << "Cipher : "<< cph<< endl;

      cout << "\nDecrypted message : "<<  (cph*ModInverse(x, p))%p<< endl;
      if ((cph*ModInverse(x, p))%p == msg){
      cout << "    Crypto successfull !!!"<< endl;
      }
}

EDIT 2:
If (x coordinate of R * e ) is less than p then with sufficient amount of cipher text of that form, can an attacker with some cryptanalysis crack it ??? I'm reading a message in blocks...

Sorry If I'm wrong !!!

Every help will be appreciated!!!

It does not matter what encoding scheme you use for the message, as long as it is reversible: you should be able to recover the message from e.
Assume you do not know $e$ or $R_x$ (the x-coordinate of $R$). You are given $$e \cdot R_x \mod p$$
For any possible message $e'$ that you could guess, there is some integer $n$ such that $$e'\cdot n \equiv  e \cdot R_x \mod p$$
(exercise: what is this $n$?)

If you could determine which of $e$ and $e'$ was the correct message, then you would be able to tell which of $n$ and $R_x$ is the correct x-value of the shared secret $R$. But we assume that the attacker is not able to distinguish $R$ from a random point on the curve (this is the Decisional Diffe Hellman assumption).

Essentially, you do not need to worry about an adversary "factoring" $R_x \cdot e$, because in the integers mod $p$ there is not a unique way of factoring a number, for exactly the same reason that there is no unique way of factoring into rational numbers: $6 = 3\cdot 2$, but it also equals $4 \cdot \frac{2}{3}$ or $95 \cdot \frac{6}{95}$


Global minimum based cryptography? When using the Back propagation Algorithm for Machine Learning, it is often said finding the global minimum of a cost function over $\mathbb{R}^n$ is very hard, and as $n$ increases it gets even more complex. I was just wondering if there are any schemes that utilise this property.

If you look at it from the right direction, lattice-based crypto (and the Shortest Vector Problem) can be viewed as a 'global minimization' problem.