Construct IND-CPA secure encryption scheme by combining two given schemes I have two encryption schemes $\Pi_0, \Pi_1$, at least one of them is IND-CPA secure but I don't know which one. The task is to construct a scheme $\Pi$ that is guaranteed to be CPA secure and to provide a proof for this.

Despite reading q1, q2 I still don't understand the best way to construct the scheme and how to fully prove its security.

Any ideas or hints into the right direction are appreciated!

The first remark is that the cryptosystems are used with independent keys. This is important, otherwise it is usually very hard to prove anything.

The simple solution

Now, the simple solution is, as is mentioned in the comment and the linked question, is to secret-share your message into two shares and encrypt each share separately. The final ciphertext consists of these two ciphertexts. (This can also be phrased in terms of a "one-time-pad" encryption, but it is better to think about it as a secret sharing, since it is then trivial to generalize to the case where you have more than two cryptosystems.)

The proof strategy is straight-forward. In order to learn anything about the message, an adversary needs (the same parts of) both shares. If at least one of the cryptosystems are IND-CPA-secure, the adversary can learn nothing about at least one of the shares. IND-CPA-security follows.

A proof based on games would probably first use real-or-random (RoR-CPA, equivalent to IND-CPA) for the secure encryption scheme to encrypt a random string instead of the secret share. Once this is done, the properties of the secret sharing guarantees that the adversary cannot learn anything about the message.

As for secret sharing, the simplest is usually the best. If your message is $m$, choose a random string $r$ of the same length. The random string is your first share. Then compute the xor of $m$ and $r$, this is the second share. (This generalizes to more shares in the obvious way by choosing more random strings.)

Composition

A more complicated thing happens if you try to compose the cryptosystems in the sense that you first encrypt the message with one system, and then encrypt the resulting ciphertext with the other system.

If you encrypt with the secure system first (the importance of being first!), everything is ok. Anything the second encryption does, an adversary could have done, so the second encryption cannot destroy the secure inner encryption.

What about if you encrypt with an insecure system first? The intuition is that the outer system (which is now secure) should hide the insecure ciphertext, which would then make the composition secure. But this is not true, and the problem with your intuition is that a cryptosystem hides the message only up to message length. What can happen is that the insecure cryptosystem produces ciphertexts whose length depends on the message. That length (which contains information about the message) can leak through the secure cryptosystem and result in an insecure construction.

However, if you restrict your attention to some sort of "length-preserving" cryptosystems, where the ciphertext length is a function of the message length only, not on the exact content of the message, then your intution should work again.


Timestamps, sequence numbers, and nonces for replay attack What are the best practices or standardized methods to prevent replay attacks in a simple server client setup (preferably where the server is stateless) ?

When should timestamps, sequence numbers, and nonces be used, and what is the main purpose/differences between them?

AEAD constructions encrypt messages and append an authentication tag. That authentication tag is computed using the following data:

The secret key
The nonce
The message, before or after encryption
Optionally, some additional data

During the decryption process, the authentication tag is computed using the same data, and compared with the one that was attached to the ciphertext.

In order to prevent replay attacks, one of these parameters has to be implicitly known by the recipient.

A simple way to ensure that is to set the initial nonce to a given value, and increment it after every message.

The originator only sends the initialization vector. Individual messages do not contain a copy of the nonce used to encrypt them. They don't have to, since the recipient can perform the same operation as the sender, namely increment the nonce after every received encrypted message, in order to decrypt the stream.

If the stream being decrypted doesn't match the original stream, because messages have been altered, removed, added, duplicated or reordered, the authentication tag will not match the one computed by the recipient using the expected nonce. This issue will be immediately detected by verifying the tag.

When using a transport protocol such as UDP, encrypted messages are not guaranteed to be received in order. Some datagrams may also be missing or duplicated. Applications must reorder them and handle retransmission.

In that situation, a copy of the nonce, or value representing the difference with the initial nonce, can be added to every encrypted message. Since a message is encrypted and authenticated using a unique nonce in addition to the key, the decryption process will immediately detect a an encrypted message whose attached nonce has been tampered with.

Now, if the server is "stateless", there are no ways to ensure that a message hasn't been received before. However, it is still possible to check that a received message is not too old (with the definition of "too old" being application-specific).

Attach a timestamp to the message or to the ciphertext. If it is attached to the ciphertext, include it is the additional data, so that it will be part of the computation of the tag.

The recipient can then check that the timestamp has not been tampered with, and that it is not older than expected.

This requires synchronized clocks, and once again, only provides partial protection against replay attacks.


Entropy of system data - use all and hash, or trim least significant bits? I'm working on a background entropy collector for key generation that monitors hardware and produces an entropy pool.

Here's my list of sources:

Mouse position
Keyboard timings (i.e. time between keystrokes)
Network

Bytes sent
Bytes received
Datagrams sent
Datagrams received

Processor (per CPU)

Interrupts/sec
Queued DPCs/sec
C3 Transitions/sec

Memory

Page Faults/sec
Transition Faults/sec

Disk

Write bytes/sec
Read bytes/sec

Process (total)

IO Read Bytes/sec
IO Write Bytes/sec
IO Other Bytes/sec
Page Faults/sec

USB

Interrupt Bytes/sec
Controller PCI Interrupts/sec

Time taken to fetch all of the above data (measured using QueryPerformanceCounter)

These stats are collected once every 330ms. At the moment, I'm just globbing all the data into an array of around 100 bytes. I then hash the array using SHA512, to add a total of 64 bytes to the entropy pool, giving me roughly 200 bytes per second.

The pool is initially populated by the hash of a single timestamp value indicating the system boot time. When the pool reaches 64KB, I xor with the oldest 64-byte block. This is somewhat warned against in another question, but I don't foresee a problem because the pool is very large and the reasoning for removing old data is size. Keys are generated by computing a cryptographic hash of the entire entropy pool.

This seems reasonable, but I wonder whether SHA512 is overkill. Would I be better off extracting the least significant bits of each statistic into a bitstream? If so, how many? Are there any other issues with my approach?

What you are doing sounds a lot like what the /dev/random and /dev/urandom or the PRNGD on many systems already do:
those systems take an arbitrary large sequence of numbers (from a true hardware random number generator if available, or else from environmental noise such as keystroke timing)
and feed it into a CSPRNG.
The CSPRNG internally maintains an "entropy pool",
and thoroughly "mixes" the pool whenever it produces a new output value.
The output is made available via /dev/random and /dev/urandom .

Have you considered possibly using the /dev/random or PRNGD already running and available on your system?
Have you considered possibly downloading the source code to some CSPRNG that has already been written, tested, debugged, and checked for security flaws, rather than writing your own from scratch?

At the moment, I'm just globbing all the data into an array of around 100 bytes. I then hash the array using SHA512, to add a total of 64 bytes to the entropy pool
Would I be better off extracting the least significant bits of each statistic into a bitstream?

Rather than collecting a batch of data, hashing it, and then feeding that into the CSPRNG,
it's better to simply feed the batch of data directly onto the CSPRNG.
(The CSPRNG already handles the "hashing" stuff internally).
At best, your hash operation preserves whatever entropy exists in the source data;
at worst, it is unnecessarily throwing away some of that entropy.
SHA512 is an excellent hash function, so hashing the incoming data with SHA512 is OK but unnecessary.
(The idea of "XOR all the collected bits" seems to throw away too much entropy).
The high-order bits of most of those statistics have very little usable entropy -- however, assuming the CSPRNG is properly written, that doesn't hurt anything.
A properly written CSPRNG is just as secure even when one of the inputs doesn't have any entropy -- such as an input that is always "000000000000000...".
If, hypothetically, you are forced to cut back on the number of inputs to your CSPRNG in order for some reason,
you would want to preserve as much entropy as possibly by cutting out such zero-entropy (all-zeroes) and low-entropy (high-order bits of these other stats) before cutting out higher-entropy sources.

When the pool reaches 64KB...

Wow. That many bits in the entropy pool is overkill in our universe.

Keys are generated by computing a cryptographic hash of the entire entropy pool.

Yes, that's how most CSPRNG produce their output values.

FreeBSD and AIX implement /dev/random using the Yarrow algorithm
OpenBSD implements /dev/random using an algorithm based on RC4 (is this the same as ISAAC ?)
Fortuna
My understanding is that many other CSPRNG implementations have a way to feed in more bits of entropy.

(I'm re-using a lightly edited of a previous answer I wrote,
PRNG taking advantage of very large seed
)


Repeating something encrypted and non-encrypted? If one wants to keep the receiver's name non encrypted, but it also appears in the encrypted message - will it leak information? (other than the receiver's name, of course.)

Let's assume a "bad" case - where there are many messages to the same person, and that the name in the encrypted message will always appear in the exact same place, and will be publicly known to be there.

Of course it doesn't matter whether it's a name, or any other information that will be present in both encrypted, and non-encrypted form.

No, it won't "leak" information, as long as you're using a modern symmetric algorithm that's resistant to known-plaintext attacks.

However, depending on the encryption mode used (and whether there's integrity checking or not), there can be other security implications, such as the data in the known spot being substituted.


What is DLf3072s256mRijndael cipher suite? We have a Thales HSMS and upon going into the Cipher Suite, we have the DLf3072s256mRijndael cipher. What is this cipher and how does it work?

Is this an AES encryption? What does DLf mean? what about s256m?

The only information I can find is on here

Guessing:

DL -> Discrete Logarithm
f -> finite field (of prime order)
3072 -> size of finite field in bits
s -> (not sure) SHA?
256 -> size of hash digest or subgroup size (used in DSA the old Digital Signature Algorithm?)
m -> don't know honestly.
Rijndael -> AES.


HMAC-SHA-256 vs SHA-512/256 vs truncated SHA-512 for use as a MAC I'm looking at three options for shared-secret message authentication codes:

HMAC-SHA-256(secret, payload)
SHA-512/256(secret+payload)
SHA-512(secret+payload) truncated to 256 bits

Option 1 is the most standard choice.  I'm considering option 2 because it is faster on 64-bit CPUs.  I'm considering option 3 because SHA-512 is more widely available in programming language libraries than SHA-512/256.

Are options 2 and 3 appropriate for MACs?  Are there any security-related reasons to pick one over the other?

Clarification: I realize that a good HMAC-SHA-256 implementation is not significantly slower than SHA-256.  I'm considering options 2 and 3 because SHA-512 is faster than SHA-256 on 64-bit machines (link).

Background: Some cryptographic hash functions (like SHA-256 and SHA-512) are "length-extendable".  This is not necessarily a problem because correct uses of a hash function should not be affected by that property.  But you can't use such a hash function directly as a MAC because, in that use case, the signature and input both come from an untrusted source (length extension attack).

SHA-512/256 is a hash function based on SHA-512 that is not length-extendable.  (It's similar to running SHA-512 and only using the first 256 bits of output, which is also not length-extendable.)  My question was whether these two hash functions could be directly used as MACs.

Option 2 and 3 are appropriate for a MAC, assuming the length of the key is not variable (otherwise appropriate padding must be used, similar to that used in KMAC). In this manner, it behaves like SHA-3 which does not need to be run in the usual nested HMAC construction. Numbers 2 and 3 are actually virtually identical. The only difference is that SHA-512/256 uses a different IV than plain truncated SHA-512. They all provide protection against length extension attacks.

Note that you can optimize HMAC to reduce the number of calls to the hash. Any decent implementation will not have significantly impaired performance compared to HMAC-SHA-256. You can also get away with only executing a single SHA-256 function using an older construction called an envelope MAC which concatenates the key, message, and key again, with padding.


What is the adversary advantage for soundness of a sigma protocol? Does a sigma protocol have an adversary advantage of zero for soundness? Or is this affected by the probability distribution of the indistinguishability of the simulator? Will in that case using the Fiat-Shamir heuristic affect the adversary advantage?

No, the advantage of an adversary against soundness in a $\Sigma$-protocol is not 0. In fact, a $\Sigma$-protocol satisfies honest-verifier zero-knowledge, meaning that one can always "cheat" by running the zero-knowledge simulator against an honest verifier, provided that we manage to guess the challenge in advance. This means that any $\Sigma$-protocol will have soundness error at least $1/|S|$, where $S$ is the set of all possible challenges. Most $\Sigma$-protocols from the literature actually achieve this bound exactly.


Decrypting AES256-CBC with wrong encryption key Using OpenSSL library is there any chance that decrypting AES256-CBC encrypted data with wrong encryption key will succeed without an error?

Asking this because I have read somewhere there is 1/256 chance that decrypting broken data won't produce an error

Yes, that's correct, decrypting altered ciphertext data or data with the wrong key may result in the wrong plaintext without producing an error. Actually, the chance is slightly more than 1/256.

First of all, we need to assume that the data is still a multiple of the block size. If it isn't then it won't decrypt at all.
Furthermore, if the key is correct and the last (and the last few bytes of the first-to-last) ciphertext block are correct then the decryption will not fail, even though the resulting data in the first blocks may be incorrect.
If the data is a multiple of the block size then the AES-CBC decryption will never fail. However, OpenSSL uses PKCS#7 padding by default - that is if the high level EVP functions are used instead of the lower level AES functionality. That means that the plaintext data is always padded before being encrypted, even if the data is a multiple of the block size. This is also true for the command line interface of OpenSSL by the way.

During PKCS#7 unpadding there is a 1/256 chance that the decryption of the last block ends with 01 if the key is incorrect or if the last ciphertext block is incorrect.
However, there is also the chance that the last block ends with 02 02 which is also valid padding. The chance of this happening is however just 1/65536 so it is almost negligible compared to the chance that the last decrypted block ends with 01. This is even more true for 03 03 03, 04 04 04 04 of course. As padding / unpadding must always be performed according to PKCS#7 the chance that a random ciphertext block is accepted is therefore close to 1/256.

An adversary can always change any ciphertext block up to the last as the error propagation properties of CBC are limited to the current block and (part of) the next block. You need to authenticate the ciphertext to avoid this and to avoid padding oracle attacks where those are applicable. For that, calculate a HMAC over the IV and ciphertext or to switch mode to e.g. GCM and perform the necessary verification before decryption.


Why is the server's public key always used in SSL encryption and never the client's public key? I spent a lot of time looking for an answer to this question, but the majority of answers never explicitly explain why the client's public key is never used; it's always the server's public key that's used in SSL encryption. Similarly-phrased questions (such as this, this, and this) don't actually explain why the server's public key is not used. Rather, they just explain why public-key encryption is not used for the actual messages, or they explain some other topic instead.

So, my question is: why do we not use the client's public key in SSL encryption instead of using the server's public key? Theoretically, it shouldn't matter whether the client's public key or the server's public key is used, right, since in either case a master secret key is always established?

Why is the server's public key always used in SSL encryption ...
  ... why do we not use the client's public key in SSL encryption instead of using the server's public key?

Neither the servers nor the clients public key is used for encrypting application data.

The servers public key is only used for encrypting the premaster secret during the obsolete RSA key exchange. And this is done since this way the server gets implicitly authenticated because only the server can decrypt the encrypted premaster secret using its (the servers) private key. And proper authentication of the server is essential to protect against active man in the middle attacks.

Apart from that there usually isn't even a client key involved in TLS. A client key is only involved when mutual authentication is done, i.e. when the client is required to authenticate against the server using a client certificate. Thus, in most cases the client does not even have a key.


Which asymmetric cipher provides the highest performance? To get the highest performance, which asymmetric cipher provides the fastest encryption/decryption? ECC or DH? What key size is recommended today?

I prefer a ~128 bit security level. With ECC this means a curve with ~256 bits, with DH or RSA this corresponds to around 3000 bits. If you can accept a lower security level, the advantage of ECC over DH/RSA gets smaller.

My favourite is Curve25519, which has easily available high performance implementations. An alternative is P256 which is a NIST standard, but a bit slower. There are also some other curves/implementations which are faster than Curve25519, but those seem more academic.


Best way to generate a IV for AES-CBC when encrypting files? The situation is that I want to use symmetric encryption to store some info in files. I'm going to use AES-CBC algorithm. The user is going to remember the password (meaning it will not be stored anywhere but in the brain of the owner of the files) however I'm worried about the management of the salt and the IV.

From several sources I've seen that the salt must be unique and never reused (which imples using a cryptographically secure pseudorandom number generator) but it can be safely appended in clear text to the encrypted data. Is this right?

For the IV I have seen two different approaches:

Similar to the salt, generate in randomly and store in clear text.
Derive it from the password and salt, the same way it is done with the key used to encrypt each block via the AES algorithm.

Which is the preferred / safest way?

Generate a random IV (with a cryptographically secure random generator of course) and prepend the IV to the ciphertext.

Some modes of encryption don't require a random IV, but you can never go wrong with a random IV as long as your RNG works fine. An IV does not need to be secret (it's a matter of terminology — if it had to be secret it woulnd't be called an IV).

In the case of CBC, a non-random IV is safe if the key is only ever used for a single message. Your key is apparently derived from a user password and a salt, which makes it unique for this password-salt combination — but are you always going to generate a new salt when you encrypt a new version of the file? Even if you currently do this, are you sure that version 3 of your program isn't going to do things differently and encrypt several files with the same key?

Use a random IV, generated independently from the salt. The maintenance cost is negligible and arguably negative (it's one line of code, less long than the comment explaining why it would be safe to use a non-random IV), the performance cost is negligible.

Don't forget that CBC only ensures confidentiality, it doesn't protect the file against modification. Strongly consider using an authenticated encryption mode instead, which protects both the confidentiality and the authenticity of the data.

Finally, or rather firstly, there are already plenty of libraries and plugins to do this out there — do you really need to reinvent the wheel?


Can hashes be used to generate larger random numbers? As far as I understand a hash transforms data into a fixed length representation. For example, a random function returns 8-byte numbers and a hash function has a block size of 32-bytes. If I now generate the hash of each random number, would the resulting hashes be an evenly distributed set of random numbers with a length of 32-bytes? I know one could simply multiply the random number by 4, but this would result in the same random entropy as before.

No, actually your 32-bytes would only be a representation of the 8-bytes random (or pseudorandom) number. In this case if I want to attack you system (eg. by brute force) I need only to perform 2^8 attempts instead of 2^32 as someone could expect. This occurs because the 32 hash is only a deterministic representation of a very small 2^8 number.


Probability of collision in PRF My question is related to this:

Collision-resistant Pseudorandom function

Assume we have a pseudorandom function as follows: $PRF: \{0,1\}^{l}\times\{0,1\}^{t}\rightarrow\{0,1\}^{m}$, where $l$ is the security parameter. Also, assume $k,k'\leftarrow \{0,1\}^{l}$ are two independent random keys and $r_1,r_2 \leftarrow \{0,1\}^{t}$ are two independent random values.

Question 1: What is the probability that $PRF(k,r_1)=PRF(k',r_2)$

Question 2: Would the probability in the question 1 be different if we replace $r_1, r_2$ with a fixed value $i$, probability that $PRF(k,i)=PRF(k',i)$?

You claim that $k$, $k'$ are chosen independently and uniformly. Assuming these keys are used nowhere else except as PRF keys in this way, and that the length of the PRF keys are at least the security parameter, then you can apply the security of the PRF. Collision resistance doesn't seem relevant to me if the key portion of the PRF input is guaranteed to be chosen randomly. The answer to your question is negligibly close to the answer to:

what is the probability $R(r_1) = R'(r_2)$ where $R$ and $R'$ are independent random functions?

Here it is clear that the distribution over $r_1$ and $r_2$ is irrelevant. The outputs $R(r_1)$ and $R'(r_2)$ are distributed uniformly/independently. So they are equal with probability $1/2^m$.

So the answer to your question seems to be ``negligibly close to $1/2^m$'' where the negligible amount is the security loss of your PRF. If $m$ is large then it is possible the PRF security loss may overwhelm the $1/2^m$ term. If $m$ is small (e.g., constant), then the security loss probably dwarfs the $1/2^m$ term.


What might be the intuition for this scheme to be AEAD and what is the problem with this? There is a plaintext message $M$, and a key $K \:\stackrel{{\scriptscriptstyle \hspace{0.2em}\$}} {\leftarrow}\ \{0,1\}^{128}$ which we will use for AES, we can extract a ciphertext $C \gets \mathrm{CBC}[\mathrm{AES}_K](0^n,M)$, i.e., CBC
mode encryption under IV $0^n$ of the message.

The master keys $L1,L2$ are shared between the sender and receiver.
Sender creates a header (associated data) $H$ that contains various
things including a ciphertext $W \gets \mathrm{AES}_{L1}(K)$, the
enciphering of the per-message key $K$ under master key $L1$. Sender also computes a tag $T \gets F_{L2}(H)$ for some function family $F$ that
we assume is a good PRF. Then the sender transmits $(H,T,C)$ to the
receiver.

A critical part of any AEAD scheme is that it ensures the authenticity of the header data and the ciphertext. Your scheme only protects the header data, leaving the ciphertext vulnerable. Protecting the key is not enough.

CBC mode is affected by certain bit-flipping attacks, that allows an attacker to change part of the message. This results in one block being completely garbled, and the next block having the exact bits flipped that were flipped in the attack. The rest of the decrypted message is untouched. If you don't authenticate the ciphertext, you will be vulnerable to this attack. This attack also extends to certain padding oracle attacks.

As for the IV and key: using a static IV with a unique per-message key may be secure, but it's a non-standard way of implementing CBC. Best case, it doesn't gain you anything over the standard way of implementing CBC. In the spirit of "Don't roll your own", it would be best to use CBC the standard way, with a random, unique and unpredictable IV.


Is it hypocritical to use AES-256 and RSA 2048 in the same application? I see a common claim that AES-256 is the gold standard and is good future proofing, often in the same wind as "just use 2048-bit keys for RSA". Security documents seem to recommend both AES-256 and 2048-bit RSA keys, and 2048-bit RSA keys are often used in the key exchange for a 256-bit AES key.

I believe:

Using AES-256 is "future-proofing" your system
Using 2048-bit keys in RSA is being practical and not worrying about future-proofing

Is it hypocritical to increase AES to 256-bit keys without increasing the RSA key length?

Using AES-256 instead of, say, AES-128 is not merely ‘future-proofing’: AES-128 provides a security level far below the standard of 128 bits today.  If your application has four billion users, the expected cost of breaking one of them by the best generic brute-force attack is about $2^{96}$ evaluations of AES-128, which can be parallelized.  This might not break your toy application, but it is well within the realm of human feasibility.  Not so for AES-192 and AES-256: even up to a whopping sixteen quintillion users, the expected cost of the same attack on AES-192 is an unimaginable $2^{128}$ evaluations of AES-192.

So if you want AES—which invites timing side channel attacks on software implementations, unlike, say, ChaCha—then you should pick AES-192 or AES-256 without further thought.  This saves you the effort of thinking about whether AES-128 provides adequate security for your application.  AES-192 and AES-256 are marginally costlier than AES-128, so if you have an overwhelming performance concern then we can discuss the finer details when you present a budget measured in joules or nanoseconds or cycles per unit of processing in your application, and not until then.

The story is more complicated for RSA, and depends on what you're doing with it:

If you're using it for signatures, you will presumably have some way to rotate signatures—unlike confidentiality, authentication generally need not last for decades.
The number of RSA keys is likely to be considerably smaller than the number of AES keys, if for no other reason than that generating an AES key costs a few dozen CPU cycles while generating an RSA key involves a search through complicated primality tests.
RSA computations are substantially costlier than AES computations at any reasonable key size, so your budget for time might actually be measured in milliseconds rather than nanoseconds, like human response times.
RSA key sizes are substantially larger than AES key sizes, so your budget for time might actually be measured in kilobytes rather than bytes.

All these considerations might figure into your application: it would not be hypocritical to pick AES-256 and then spend your time worrying about RSA, if RSA-4096 is too costly.  Heuristically, we might infer that RSA-2048 is safe for the time being because the current factorization record is RSA-768, and while we're overdue for an RSA-1024 factorization, there's a big gap from there to RSA-2048.  But it is also true that a 2048-bit RSA modulus certainly doesn't attain a 128-bit security level either.  The best cost estimate I'm aware of gives an area-time cost per key of about $2^{103}$ if we conservatively read $o(1)$ as zero, rather than the cost $2^{112}$ advertised by keylength.com, NIST, etc.

That said: Can I interest you in Ed25519 or X25519, which confidently provide a 128-bit security level—meaning the best attack has expected cost $2^{128}$ curve additions no matter how many users there are—with 32-byte keys and 64-byte signatures, and at much lower cost to generating a key or making a signature or decrypting a message than RSA will ever attain?  Then, unless your bottleneck is verifying signatures or encrypting messages, you don't have to spend time thinking about whether RSA-2048 is secure enough as you use it in your application.  (See also this earlier answer to a similar question about AES-128 and X25519.)


How do I correctly derive a Key and IV? Mainly I'm trying to understand how to correctly create the Key and IV for use with the .NET Implementation of AES (AesManaged class).

This encryption code will be used in conjunction with existing customer records in a database.

Here is the process that I've come up with.  First, get the key from an encrypted web.config and get a byte array using the Rfc2898DeriveBytes class.  The salt is a constant.

public static byte[] GetKey(string key)
{
    var deriveBytes = new Rfc2898DeriveBytes(key, _salt);

    return deriveBytes.GetBytes(32);
}

Next, generate another byte array for the IV given the User's ID and the same salt from above.  This method is essentially the same, but returns an array with 16 bytes instead of 32 (and the input is the User ID, not the key).

public static byte[] GetKey(string text)
{
    var deriveBytes = new Rfc2898DeriveBytes(text, _salt);

    return deriveBytes.GetBytes(16);
}

Given the Key and the IV I use a CryptoStream to encrypt the data:

var aesAlg = new AesManaged();

// Create an encryptor to perform the stream transform.
var encryptor = aesAlg.CreateEncryptor(key, iv);

// ... Code that uses the Crypto Stream

Main question(s):

Is there a better/different class that I should be using instead of Rfc2898DeriveBytes?  It seems funny that the class name references an RFC.
Is the use of a constant salt bad?  I'm doing this so that I don't need to store any additional information on the User record.  Other examples I've seen use a constant IV, but a random Salt.  Are those 2 scenarios essentially the same?

Cryptographically speaking, AesManaged uses AES in CBC mode. To ensure this operates securely, you need to choose the IV randomly, i.e. it should not be possible to predict the IV between iterations. This question has a discussion of non-random IVs:  Using a Non-Random IV with modes other than CBC and this SO question: Why is using a Non-Random IV with CBC Mode a vulnerability? has a discussion about the chosen plaintext vulnerability using non-random IVs.

According to the documentation, Rfc2898DeriveBytes implements PBKDF2, a key stretching function. DeriveBytes is an interesting choice of name, but that's essentially what it'll do - output some bytes from the PBKDF2 algorithm. At its heart, PBKDF2 is a repeated application of SHA1; if you input the same passphrase and IV, you'll end up with the same encryption key.

Unlike a hash, you're not going to be storing this anywhere, as it is your secret key for your symmetric operation, so there's less risk of an attacker trying to find a preimage (recover the passphrase) mostly because they just don't need to. So the uniqueness requirement looks unnecessary - however, hypothetically speaking let us assume for a minute all your users use the same passphrase "I love asking crypto questions on SE". If they do this and you're using a constant salt, they'll have the same key. Non-repeating IVs for our CBC mode will mitigate the problem slightly, but it would be a lot better if the keys weren't all the same in the first place.

So, summary:

Constant Salt: bad. Pick a large salt, unique per user. Randomly picking salts will help you achieve this - if you generate a 64-bit salt that gives you a total possible output space of $2^{64} = 18446744073709551616$, or approximately $2635249153$ unique salts per human being right now. So you are not likely to run out, and guarantee that all your user's keys are unique assuming no collisions in PBKDF2.

Edit thanks to fgrieu - the salt size must be 8-bytes (64-bits) or larger. If you can accommodate larger salts, you should, to avoid birthday attacks. For more information, see the comments.
Constant IV: bad. You definitely want a random IV for CBC mode.


Can you explain the counter in the Key derivation function of PACE? I try to understand the PACE-Protocol, especially the Key Derivation Function in ECDH on page 33.

Can someone explain me, what the Counter is good for? Often there are iteration counters in KDF - but here are usual Hash-Functions (like SHA-256) are used as KDF. So there is no iteration. Is this something like a message counter so that we create a new Hash for every new message?

The counter is used to distinguish the different (session) keys used in the protocols. A relatively standard KDF is used, KDF2. Note that only a single iteration is needed and that no OtherInfo has been defined, so the specification of KDF2 may look more complex than it is in the PACE protocol. A 32 bit counter is of course overkill for the protocol, but that's just how the counter has been defined.

So you have the counter valued 1, encoded as 00000001 in hexadecimals as input for the encryption key, and a counter valued 2, encoded as 00000002 for the MAC key.

Some of this is explained in the very first sentence of A.2.3, page 33 (the definitions of KDFMAC and KDFENC).

Note that this counter is entirely different from the Send Sequence Counter used within the secure messaging protocol. That counter is either 64 or 128 bits in size.


Clinet's nonce in TLS In TLS, both client and server send nonces int heir hello messages. How the server identify whether the client hello is replayed or not? does the server maintain cach of previous nonce? for how long? can you clarify the mechanism to me as I do not find these details in the standard documentation.

Your confusion comes in who the client's nonce is protecting. The client's nonce protects the client from server replays. Similarly, the server's nonce protects the server from client replays. This makes it so that neither has to remember past nonces. As long as the client is implemented correctly and does not reuse a nonce, a server trying to replay a message will fail.


Families of elliptic curves I was reading this paper about elliptic curves and I saw this graphic:

This paper is pretty new (november 2018) and I was wondering, whether these are all known ecc-families or not. The key point is, that I don't see Weierstraß curves. Can someone explain to me, why Weierstraß-Curves are not included? Are there other curve-families that are not included. If true, which?

For elliptic-curve-based protocols, it is assumed that finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is infeasible: this is the "elliptic curve discrete logarithm problem" (ECDLP). The security of elliptic curve cryptography depends on the ability to compute a point multiplication and the inability to compute the multiplicand given the original and product points. The size of the elliptic curve determines the difficulty of the problem.

We can formally define an elliptic curve (over a field k) is a smooth projective curve of genus 1 (defined over k) with a distinguished (k-rational) point. However, not every smooth projective curve of genus 1 corresponds to an elliptic curve, it needs to have at least one rational point. The definition of the elliptic curve also requires that the curve be non-singular. Geometrically, this means that the graph has no cusps, self-intersections, or isolated points.

There is an infinite number of elliptic curves, but a small number that is used in elliptic curve cryptography (ECC), and these special curves have names. Apparently there are no hard and fast rules for how the names are chosen, but there are patterns. IETF has published a report on the list of alternate elliptic curve representations recently. You can refer to the IETF report here. Following are some of the reference elliptic curve families. A few of them are missing in the diagram.

Curves in short Weierstrass form
Montgomery Curves
Twisted Edwards Curves
Supersingular Edwards Curve
Hessian Curve
Twisted Hessian Curve
Jacobi Quartic Curve
Doubling-oriented Doche–Icart–Kohel Curve

Elliptic Curves were originally written in Weierstrass form. Edwards elliptic curves have their own advantages: addition, doubling and tripling can be done faster on Edwards curves than on curves given by a Weierstrass equation. This is because the addition law on Edwards curves does not have exceptions, while the addition on Weierstrass curves
distinguishes several special cases.  The Montgomery curve is suggested for application in elliptic curve cryptography because arithmetic in this curve representation is faster and needs less memory than arithmetic in standard Weierstrass form.

Please find an insightful article on the names of some the prominent elliptic curves used in cryptography.


Need help with NFC Tags and cryptography I have some NFC-Tags, which will be added to my devices. These NFC Tags are basically EEPROMs with an unique UUID (7-Byte, readonly, public) and some constant parameters (approx. 7-15 Bytes, read and writeable, also public) in it.

Can I use a digital signature in order to tell if a given NFC-Tag belongs to my devices and if the parameters haven't been changed by an evil user?  (Message for signing algorithm would be UUID + Parameters)
I'm using an 8-bit microcontroller with very limited resources on the NFC-Reader side for the verification process. Therefore the verification step should be as easy as possible (signing the tags can be done on a powerful PC). Which Algorithm would you use for this application?

Preliminary caveat: the un-clonability of your NFC tags is relative. A mobile phone with NFC is all it takes to read one, perhaps surreptitiously. Then a number of devices like proxmark3 can emulate it. A static digital signature would not prevent that.

  Can I use a digital signature in order to tell if a given NFC-Tag belongs to my devices and if the parameters haven't been changed by an evil user?

No, a digital signature can't authenticate the data in that size-constrained tag: more memory is required that the tag allows.

All digital signatures schemes add at the very least $2b$-bit of data for $b$-bit security, so for 80-bit security (which is NOT safe enough by modern standards) we are talking 20 bytes, more than the question quotes. And that's for some BLS signature schemes pushing things to the max, which (although reportedly used with great success) have not their security strongly vetted. The industry standard is $b=128$-bit security with $4b$-bit signature, thus 64 bytes (e.g. Ed25519). I know nothing well-seasoned below $3b$-bit overhead for small signed data, or $2b$-bit for larger data (above about 220 bytes).

  I'm using an 8-bit microcontroller with very limited resources on the NFC-Reader side for the verification process. Therefore the verification step should be as easy as possible (signing the tags can be done on a powerful PC). Which Algorithm would you use for this application?

Among common signature schemes, only RSA and Rabin signature have fast verification (seconds) on 8-bit microcontrollers, but unfortunately their minimal data requirement is like 2048-bit (256 bytes) for modern security. Thus you'd need 256 bytes of memory in the tag for the signature (in addition to the UUID; the rest may come for free, see below).

With RSA/Rabin per ISO/IEC 9796-2 using SHA-256, it is possible to embed payload data into the signature (e.g. up to 222 bytes for 256-byte signature), and this payload becomes available as a byproduct of signature verification, which is fast. That's RSA/Rabin signature with message recovery. It essentially achieves $2b$-bit size overhead for $b$-bit security, for a payload at least a certain size.

All common signature schemes requiring less memory are considerably slower for signature verification, in the order of a minute for 128-bit security given the low-end CPU.

Feasible options include (not exclusive, not limitative)

Using a Message Authentication Code rather than a digital signature. That solves the size and speed issues (8 bytes and a tenth of second is ample), but unfortunately a verification device contains the secret key that also allows to compute a MAC that makes a tag working. If an adversary can get hold of a verification device, these might need to be tamper-proof, thus slightly more expensive. And it can't be entirely ruled out that a verification device is successfully attacked and its secret key extracted (though that can be made extremely hard, even certified so).
Going online: the UUID can be used as index in a server, knowing if the tag is registered or not. The server can digitally sign that it vets the tag with that UUID as OK, and it can use a system with lightweight signature verification. That has the advantage of allowing a dynamic black/whitelist.


Which tamper-protection algorithm provides the shortest output? Background

When making web applications you sometimes need to pass data along with the form which isn't visible to the user. Database IDs are the most common, but texts and IDs are sometimes necessary too. For this reason there is a <hidden> field in HTML, but it has a drawback - any hacker with a basic understanding of what he is doing can modify the value. It would be better if such values would be tamper-protected, if not outright encrypted.

Question

I need to pass a value through hostile territory. The value is most often an integer (and that most often less than 65'000, so mostly just two non-zero bytes, rarely three, almost never 4). However sometimes the value can also be a string (short, a few hundred characters at most). I'm OK with using different algorithms for different kinds of data.

I want to tamper-protect the value, so that it cannot be changed en-route without detecting. Hiding the data isn't necessary, but doing so would be a bonus. So either tamper-protection or encryption would work.

Whatever the algorithm, I want to have the output as short as possible without sacrificing too much of security. This is because it's a webpage and shorter data means faster response times. Also, the HTML code becomes easier to read if there aren't lengthy random strings in it.

What algorithms would you suggest for this purpose?

You are writing out data and reading it back on the same server. You want to ensure that the data that you read back is the same as the data that was written out.

For this use case, symmetric cryptography seems appropriate. Have a single symmetric key that doesn't leave the server. You need to rotate the key only if the server is compromised; this will invalidate sessions in progress, which is likely to happen for other reasons in case of a server compromise as well.

You can take add an HMAC checksum of the data; with HMAC-SHA-256 (a strong, recommended choice), this adds 64 bytes if you encode the checksum in hexadecimal or 44 if you encode it in base64 (or 32 if you include it in binary form but that tends to be hard to parse). There'll probably be a few more bytes' overhead to put the string somewhere. Given the context — a web page — I don't see any point in weakening the cryptographic strength to save a few more bytes.

If you want to encrypt the data as well, use AES-128 with an authenticated encryption mode (CCM or GCM are common choices). There will be an overhead of 16 bytes of IV, up to 16 bytes of padding, 16 bytes of MAC, and a multiplication factor due to the encoding requirement since the encrypted data can use all byte values (4/3 factor for base64). You'll need to decrypt the data before doing any processing with it; in particular, if some of that data is used on the client side, you'll either need to duplicate it or to combine authenticated encryption with a MAC of that plus the client-readable data.

Note that protecting the data in this way only authenticates it — it proves that the data was produced by your server. An attacker can still take the data from one page and send it with another page, or a later version of that page. How to avoid this depends on when the data is legitimate. You may want to include the URL or the user ID in the hashed data, for example, to avoid the data being used out of context.


Using HMAC SHA256 to protect payment files in local trusted network in a project that I am working on we have been tasked with eliminating PGP while providing sufficient security to protect payment files only within the Company's trusted network.  We arrived at HMAC SHA256.  Assuming that we can keep the key private and refresh the (128 bit) key annually,  can someone comment on how difficult it would be to compute the key if an attacker got the plaintext and the hash?  The files on average are about 2mb in size.

With regards to the algorithm, HMAC-SHA256 is considered very secure. As with most symmetric algorithms it can probably not be proven secure, but that should not worry you overmuch.

The most important security consideration with HMAC is to use a time consistent compare when verifying the authentication tag. A 256 bit key could be considered for the simple reason that the overhead won't make any difference when ~2MB files are being protected.

It's probably better to focus on other parts of the system security and make sure you implement the key management well.


Method to calculating e in RSA For simplicity I choose two small primes for p and q.

p=3
q=11
n=33
Φ(n)=20

Now we need to find the public key e, which has to be coprime with Φ(n). For small numbers like these it is trivial, but how can it be done when larger primes are chosen?

This is easy, just pick $e$ as prime larger than $\max(p,q)$. As $\phi(n) = (p-1)(q-1)$ it has only prime factors smaller than $q$ and $p$.

You can also do trial and error. If $e$ is prime, the GCD test is very fast. But it is technically not necessary to choose $e$ prime. Also note that key generation is not time critical.

However, often one starts with $e \in \{ 3,5,17,257,65537 \}$ which are special primes. Then one choose appropriate $p$ and $q$.
These exponents have computational benefits as they are of the form $2^k+1$. That makes computation of the $e^\text{th}$ power fast. Note that there are attacks for small exponents, especially $e=3$. They are all related to bad implementations, i.e. padding and so on. The RSA-scheme itself is not affected.


How to decrypt RSA if ciphertext is less than the modulus and e=3? I'm given a public key. Using openssl rsa ..... I got the public key has the exponent as 3. When I calculated the size of the ciphertext, it is 8 bits smaller than the 2048-bit modulus.

How can I decrypt RSA provided I only have public key and ciphertext?

Let me know if you want the files.

"How can I decrypt RSA provided I only have public key and ciphertext?"

You break e=3 RSA.  (See pages 393 to 396.)


What is the recommended replacement for MD5? Since MD5 is broken for purposes of security, what hash should I be using now for secure applications?

That depends on what you want to use the hash function for.

For signing documents, sha2 (e. g. sha512) is considered secure.

For storing passwords, you should use one of the algorithms dedicated for this purpose: e. g. bcrypt, sha512crypt or scrypt. In order to slow down an attacker, these algorithms apply the hash functions many times with an input that is based on the number of the current round.

Scrypt takes this concept one step further and uses a huge amount of memory. Typical hardware for password cracking has access to about a couple of KB of memory, the default configuration of scrypt requires 16 MB.


If the hash of the multiplication is equal to the multiplication of the hash, how can this be used to leverage an attack? Assume a hash function $H:\left\{0,1\right\}^*\to G$ where $G$ is a group and assume that finding an inverse in $G$ is easy.

How can a preimage efficiently be found using the fact that $H(M_1\cdot M_2)=H(M_1)\cdot H(M_2)$ for $M_1,M_2\neq0$?

I've tried playing around with the group properties but I haven't gotten very far. Any direction would be appreciated.

Perform a birthday attack:

Given $y\in G$ we want to find $w\in \left\{ 0,1 \right\}^*$ such that $H\left(w\right)=y$.

Randomly choose $x\in \left\{ 0,1 \right\}^*$ and calculate $H\left(x\right)$ and $yH\left(x\right)^{-1}$. Wait until we find $a,b$ such that $H(a)$=$yH\left(b\right)^{-1}$.

Now $w=ab$: $H(w)=H(ab)=H(a)H(b)=yH\left(b\right)^{-1}H(b)=y$.


Plaintext message space in Somewhat Homormorphic Encryption scheme? Question 1: In which Somewhat Homomorphic Encryption schemes the plaintext space is defined over $\mathbb{F}_p$, where $p$ is a prime number.

It is said, in Somewhat homomorphic encryption the noise increases when homomorphic multiplication is used.

Question 2: Does this include multiplying a ciphertext by a plaintext? or just multiplying two ciphertexts?

Answer to question 1

I don't know about any somewhat (or leveled) homomorphic encryption whose plaintext space is the field $\mathbb{F}_p$.

Several schemes work over the ring $\mathbb{Z}_t[x] / \langle f(x) \rangle$, which is isomorphic to the field $\mathbb{F}_{p^n}$ when we chose $t$ to be a prime $p$ and $f(x)$ to have degree $n$. However, for security reasons, we usually are not able to chose $n = 1$.

Schemes based on integers usually have the field $\mathbb{Z}_2$ as the plaintext space and they do not seem difficult to adapt to an arbitrary prime instead of $2$.

Answer to question 2

Yes, multiplying a ciphertext by a plaintext increases the noise.

Ciphertexts in these noisy schemes are (roughly speaking) of the form $f(m) + e$, where $f$ is some function, $m$ is the message, and $e$ is the error. When we multiply a ciphertext $c = f(m) + e$ by another message, let's say $m'$, we end up with something like $f(m) \cdot m' + e\cdot m' = f(m \cdot m') + e'$, and this new error $e'$ is bigger than the original error $e$.

For instance, considerer the YASHE scheme:

Ciphertext format: $c = \Delta m + e + hs$, where $h$ is the public key, $e$ and $s$ are random polynomials.
When we multiply by a plaintext $m'$: $c \cdot m' = \Delta m m' + e m' + hsm' = \Delta m m' + e' + hs'$.

As it is said on page 11 of SEAL's manual, for the FV scheme "plain multiplication increases the noise by a constant factor that depends on the plaintext multiplier".

And I am quite sure it also happens on plain multiplication of BGV scheme.


Appending hexadecimal string for MD5 algorithm I followed the algorithm step by step in MD5 Algorithm but in the first loop of the 64 loops, I got my A as 10325476, B as 35E4F8C4D, C as EFCDAB89 and D as 98BADCFE in hexadecimal. A, b, C and D will be appended in the end to become the md5 checksum. This makes me confuse as in the first loop, the length of hexadecimal is already 9. I believe that by continuing the algorithm, B will become bigger and bigger. This means that I will not get exactly 32 hexadecimal number in the end as 8+9+8+8!=32 Am I on the correct path or my hexadecimal length of B is indicating that I am calculating wrongly?

In MD5, the addition performed on $B$ at each round is modulo $2^{32}$ (that is, only the 32 low-order bits of the result are kept); same for the additions involving $A$, $F$, $K$ and $M$ at each round, and the four additions on $A$, $B$, $C$ and $D$ at the end of the 64 rounds.

Therefore, $A$, $B$, $C$ and $D$ all remain within 32 bits. At the end of the hashing, the concatenation of their representation as 32 bits forms the final hash, which is thus exactly 128-bit.


Is it reasonable to assume that $\text{Keccak-}f[25n]$ block permutation is defined for any value of $n$? Wikipedia contains the following claim for $\text{Keccak-}f[25w]$:

  It is defined for any power-of-two word size, $w = 2^ℓ$ bits.

Although all official descriptions of Keccak do not explicitly mention well-definedness of $\text{Keccak-}f[25n]$ for any $n$ above $64$.

So I have two related questions:

Can we assume that $\text{Keccak-}f[25n]$ is a well-defined function for arbitrarily large $n$?
What stops $\text{Keccak-}f[25n]$ from being a well-defined function even if the lane size $n$ is not a power-of-two number? In this case, we can simply calculate the required number of rounds as $$12 + 2\lceil \log_2 n \rceil,$$ where $\lceil x \rceil$ denotes a mathematical ceiling function. (Of course, round constants and rotation offsets will also be recalculated for the corresponding value of $n$.)

From a standardization point of view, $\text{Keccak-}f[25w]$ (i.e. $\text{Keccak-}p[25w, r]$ with $r = 12 + 2\lceil \log_2 w\rceil$) is simply not defined in FIPS PUB 202 when $w$ is not a power of two. Specifically, the Keccak permutation is only standardized for $w = 2^\ell$ with $\ell \in \{0, 1, \ldots, 6\}$. This means that, even if you can define the permutation for other values of $w$, it will be nonstandard.

That said, if $w$ is not a power of two the permutation will be less efficient (per bit). Ideally, your processor has instructions to operate on $w$ bits. In practice, one expects $\ell \ge 3$ for most applications. This is probably the main reason why the standard/original specification do not mention other values of $w$. Also, $w$ isn't allowed (in the standard) to be arbitrarily large because that would be overkill.

From a mathematical point of view, one could also define the permutation for $w$ not a power of two (despite the lack of a good reason). Let's consider each step separately:

$\theta$ just uses xors of bits and generalizes to all $w$, but as discussed below it is not necessarily invertible.
$\rho$ rotates each word. This works for any word length.
$\pi$ is a word permutation which clearly works for any $w$.
$\chi$ is bitwise along rows, so again no problem.
$\iota$ adds a constant to one of the lanes. This step requires more changes.

The problem with $\theta$ (thanks to poncho for pointing to this) is that it is not invertible for all values of $w$. In particular, if we represent the state as an element of the ring $\mathbb{F}_2[x, y, z] / \langle x^5 + 1, y^5 + 1, z^w + 1\rangle$ as in the reference, $\theta$ can be written as

$$\theta(\alpha) = p_\theta \alpha = (1 + (1 + y + y^2 + y^3 + y^4) (x + x^4 z))\alpha,$$

Hence, we must have $1/p_\theta \in \mathbb{F}_2[x, y, z] / \langle x^5 + 1, y^5 + 1, z^w + 1\rangle$ and this not true for all $w$.

The reason why the $\iota$ function does not immediately generalize is because it adds  $\ell + 1$ round constant bits to bits $2^j - 1$, $j = 0, \ldots, \ell$. The natural generalization would be to do the same thing but with $\ell = \log_2 \lceil w\rceil$. The problem occurs when $\ell > 8$. The round constants are computed using an 8 bit LFSR. If you want more bits, you need a larger LFSR. For all $\ell \le 6$, the same LFSR is used but some output bits are ignored. So you will need to specify another LFSR...
That said, it is not even essential that one uses an LFSR to generate round constants so you could argue that this isn't a major problem.

If $\ell$ is very large, I'm also not sure if $r = 12 + 2 \ell$ rounds would really be sufficient. I'm not going to make that analysis here, though.


Montgomery multiplication without final subtraction I am looking for methods to avoid the final subtraction in Montgomery multiplication. I found this paper "A Cryptographic Library for the Motorola DSP56000 " (http://goo.gl/DHePEx) In this paper they have said that we can avoid final subtraction if we keep N(modulus)

Brett just asked & answered this question : Confused about final subtraction of modulus in Montgomery Multiplication, during modular exponentiation

You should increase $R$ exponent by $2$.
If you use $n=1024$ , increase it to be $$n=1024 + 2 = 1026.$$
Recalculate the pre-compute $R'$, based on the new exponent.
$$R' = 2^{(2\cdot 1026)} \bmod(M).$$


backward-compatible triple encryption I was asked to encrypt a message by applying backward-compatible triple encryption using the 8-bit key $k = (k_1, k_2)$ where $k_1≠k_2$.

I'm a little confused because I thought all 3 keys had to be independent for it to be backward-compatible with DES, unless by backward-compatible they were referring to something else? Thanks.

I'm a little confused because I thought all 3 keys had to be independent for it to be backward-compatible with DES, unless by backward-compatible they were referring to something else?

No, all three keys have to be identical for the EDE (encrypt-decrypt-encrypt) scheme to be backwards compatible with DES. This is called single key triple DES.

What they may be referring to is the DES weak keys. There are keys $k_1$ and $k_2$ for DES where $E_{k_1}(E_{k_2}(X)) = X$. So if you'd use triple encryption $E_{k_1}(E_{k_2}(E_{k_1}(X)))$ then you would get $E_{k_1}(X)$ if you'd use weak keys.

Alternatively, they may just mean that you currently have to use triple-DES and that you achieve backwards compatibility in case $k_1 = k_2$.


AES-CTR-MAC alternative I have to send small (~10 bytes) authenticated messages over an insecure channel. I was thinking of an alternative to the "conventional" AES128-CTR-MAC, which will take 16 bytes for the CT and additional 2 or 4 bytes for the MAC. The motivation is that I'd like to reduce the message size as much as possible.

My alternative is to use a nonce and a counter, pass it to a HASH function, xor with the PT, and then AES encrypt. This would produce the CT.

Since PT is small, I was thinking off zero padding it (with two or 4 bytes).
Then on decryption, I can compare the zero padding and use it as an authentication.

As I see it, this method is not prone to "bit switch" attack (as changing the CT will totally ruin the PT).

Do you think it's a reasonable way to do authentication? Is it enough to use a plain HASH function, or is it better to add a key to the HASH?

If, in addition, I also want to authenticate a non encrypted part of the message, It is OK to concatenate this message to the HASH input?

In addition: The transmitter and the receiver are time synchronized. and keep their internal (and equal) counter value. on each transmission, the transmitter and receiver increment their counter. The message is sent once every 10 seconds, and the receiver will accept only one packet on scheduled time. That way, the attacker can't brute force the MAC.

I can see at least one big issue with your own scheme: the attacker could cycle through as many counters until one is found that produces the same bits in the hash at the location of the padding bits used for authentication. In that case the authentication would succeed with a different nonce / counter. This problem also disallows additional authenticated data to be added to the scheme. This would be fixed by using HMAC instead of a hash. When validating the padding bits I would use a constant time compare to be on the safe side (I don't see a direct issue, but better safe than sorry).

You need to pad to the end of the block anyway otherwise you cannot XOR with the hashed IV. So you should at least use as many zero bits as possible. For two bytes you have a chance of one in $2^{16}$ that a random message is accepted. That's too large for most cryptographic systems.

So for a fixed sized message you could use 4 bytes minimum, giving you a chance of one in $2^{32}$ - somewhat over 4 billion in the short scale - to accept a random message. Even then it would be a good idea to implement additional ciphertext messages. Your messages would 12 bytes of course, as the AES block size is 16 bytes in size. The larger the padding the better.

Truncating a MAC (over the ciphertext) is common. It has the same problem as validating the padding in your scheme: if you check too few bits then the message may be accepted with a probability that is considered too high. It has the advantage of being secure for variable size messages, at the obvious cost of bits compared to your scheme.

Older triple DES schemes usually use 4 bytes / 32 bits. This could be OK if an authenticated session is broken if a bad packet is received, but remember that sending $2^{32}$ random messages is commonly not out of reach to an attacker.

I'd say that having a 10 byte cipher text (for a 10 byte message, there is no need to use 16 bytes for a 10 byte message) for AES-CTR and a 4 byte MAC is more secure than your proprietary scheme. CCM and EAX are ready made AEAD schemes that could be useful in your situation. They rely just on AES and allow shorter tag sizes without losing too much security, and they allow additional authenticated data as well.

The addition (having the counter and time synced) does make it harder for an attacker to have an invalid message accepted. However, it still doesn't disallow attacks on additional authenticated data that gets hashed. It should be noted that keeping a nonce and the time synchronized can be a deceptively hard problem. An attacker is often capable of power cycling devices, slowing down clocks etc.


What does this Authentication protocol achieve and what information is shared? I'm having trouble with the following question from my class:

  "What is the purpose of the protocol, and how does it achieve this purpose and what shared information does A and B end up after running an instance of this protocol?

  $\sf A \to B: \quad A, N_A$
  $\sf B \to S: \quad B, \{A, N_A, T_B\} K_{BS}, N_B$
  $\sf S \to A: \quad \{B, N_A, K_{AB}, T_B\} K_{AS}, \{A, K_{AB}, T_B\} K_{BS}, N_B$
  $\sf A \to B: \quad \{A, K_{AB}, T_B\} K_{BS}, \{N_B\} K_{AB}$"

If anyone can help at all, I would greatly appreciate someone going through this question with me. It's not homework, it's not coursework. It's off a previous sheet of in class exercises that my teacher wouldn't go through with me.

I understand basic primitives, but I don't feel confident in my ability to look at an entire protocol and analyze its security properties.

See also How to attack this authentication protocol from "Cryptography: An introduction" for a more specific question about the same cryptographic protocol.

From my understanding, this protocol makes use of a trusted third party in order from A and B to exchange a symmetric key, $K_{AB}$. For the protocol to work, it is assumed that both A and B must share a master key, $K_{AS}$ and $K_{BS}$ respectively with the trusted S and A wants to communicate with B but they has no shared secret. Since there is no MAC/signature appended so it is implicit that the underlying encryption scheme also provides integrity checks. And a plaintext attack resistant encryption scheme should be used since the encrypt plaintext in step 4 is known. Thus,

A sends a random nonce, $N_A$ to B in step 1.

B sends its own nonce, $N_B$ and encrypt A's nonce before sending them to S in step 2.

Next, trusted server S will generate a symmetric key, $K_{AB}$ (which I guess should be a session key) and encrypts $K_{AB}$ separately with the keys shared with A and B in step 3. A can then decrypt $\{B, N_A, K_{AB}, T_B\}K_{AS}$ using the master key shared with S and verify that the nonce $N_A$ and timestamp is correct (for freshness) and B's ID is correct (to prevent MiTM attacks). Now A has knowledge of the assigned session key $K_{AB}$ and he computes an Authenticator (as called in Kerberos) which is actually the encryption of $N_B$. This allows user B to verify that user A does indeed have knowledge of the session key $K_{AB}$.

If everything is correct then A will forward the second part $\{A, K_{AB}, T_B\}K_{BS}$ to user B and also send the Authenticator in step 4. Similarly, user B will be able to decrypt $\{A, K_{AB}, T_B\}K_{BS}$ with the master key shared with S. B checks if A's ID and the timestamp is valid and retrieves the session key $K_{AB}$. Next, B uses $K_{AB}$ to decrypt the Authenticator to authenticate user A.

Currently, only unilateral authentication is provided. But an extra step
$B \to A : \{N_B +1\}K_{AB}$ may be added for mutual authentication.

The well establish Kerberos protocol uses a similar albeit more complicated concept to issue tickets for authenticated users.


Generator of one-way functions Please pardon my question if it seems silly, but I am very keen on knowing: in applied cryptography, there is such a thing as a one-way function, which given an input would generate an output that is unique for that input.
Discrete logarithms and factorials are, as far as my knowledge goes, necessary to create one-way functions.
That being said, is there a way to create random one-way functions, so that:

each of them would give the same output for the same input
and, each of them would be sufficiently unique to the others?

Many thanks

a one-way function, which given an input would generate an output that is unique for that input.

A one-way function does not guarantee uniqueness of outputs.
The definition of a one-way function gives us that given an output $y = f(x)$, is hard to find any preimage $x^*$ of $y$ for which $f(x^*) = y$ holds.

Discrete logarithms and factorials are, as far as my knowledge goes, necessary to create one-way functions.

Factorials? You probably mean the factoring problem? I haven't head of any crypto that uses factorials.
We don't know if these are necessary.
Ciphers like AES are one-way, given that the adversary doesn't have access to the key: it's hard to find any plaintext that encrypts to a given ciphertext. However, we don't have a proof that these symmetric primitives are in fact secure.
Additionally, we don't even know if they are sufficient.
If P = NP, one-way functions don't exist. Neither DL nor factoring would be computationally hard problems.

That being said, is there a way to create random one-way functions, so that:
each of them would give the same output for the same input
and, each of them would be sufficiently unique to the others?

Is your first requirement, that the function is indeed a function? I.e. that whenever you supply an input $x$ to the function $f$ you will always obtain the same output?
If so, then yes - all one-way functions are functions.
As for your second constraint - you would have to specify some metric for sufficiently unique.
In the random oracle model, it is easy to construct such a function:
Given $H(\cdot)$, a function that behaves like a random function, we can construct a function family $H_s(x) = H(s \| x)$ (where $\|$ is concatenation and $s$ a random string $\in \{0,1\}^n$ for some length $n$).
Each of these functions $H_s(\cdot)$ will behave as a random function, is different from every other function, and will be hard to invert.
I'm not sure if I've answered your question fully, let me know if I should elaborate on some part or have misunderstood your question!


Secure blinding factor switching at malicious server-side (Switching in One Time pad) Suppose all the values and operations are defined over a finite field $\mathbb{F}_p$ where $p$ is a large prime number. Assume all values are non-zero. Here $(z)^{-1}$ denotes multiplicative inverse of value $z$.
We give away the values $v_1$ and $v_2$ to an adversary and ask him to compute their product:

$v_1=a\cdot z_1$
$v_2=b \cdot z_2 \cdot (z_1)^{-1}$

So, the adversary computes $v_3= v_1\cdot v_2=a\cdot b \cdot z_2$.
The values $z_i$ are picked uniformly at random from the field. But $a$ and $b$ are fixed values of the field.
Questions:

Given the three values $v_3, v_1$ and $v_2$ can the adversary learn anything about the fixed values $a$ and $b$ (and the $z_i$ values)? If yes/no Why?
In other worlds, given the above three values, can the adversary infer anything about $a$ and $b$?

Let $v_1=a\cdot z_1$ and $v_2=(z_1)^{-1}\cdot z_2$.
If we give $v_1$ and $v_2$ to the adversary and ask him to compute their product:  $v_3=v_1\cdot v_2=a\cdot z_2$ would it learn the secret value $a$ (and $z_i$ values)?

I'll answer question 2, leaving the first as an exercise to the reader. I'll do this on intuitive grounds, rather than using explicit conditional probabilities.

The adversary is free to compute $v_1\cdot v_2$ regardless of what we ask, therefore removing everything about that and $v_3$ does not change the problem, which reduces to:

  We somewhat have chosen some $a\in\mathbb F_p$. We draw a random uniform secret $z_1\in\mathbb F_p^*$ (so that it's inverse ${z_1}^{-1}$ is well-defined) and a random uniform secret $z_2\in\mathbb F_p$, and compute and reveal $v_1=a\cdot z_1$ and $v_2={z_1}^{-1}\cdot z_2$ to the adversary; what does that reveal about $a$?

Lemma 1: for unknown $u\in\mathbb F_p^*$, drawing a random uniform secret $z\in\mathbb F_p$, and revealing $v=u\cdot z$, reveals nothing about $u$.

Lemma 2: for unknown $u\in\mathbb F_p^*$, drawing a random uniform secret $z\in\mathbb F_p^*$, and revealing $v=u\cdot z$, reveals nothing about $u$.

Proof follows from the fact that $z\to u\cdot z$ is a mapping over $\mathbb F_p$ (for lemma 1) or over $\mathbb F_p^*$ (for lemma 2).

Notice that neither $v_2$ nor $z_2$ are involved when we compute and reveal $v_1=a\cdot z_1$. Therefore, we can consider in isolation the part of the protocol where we draw a random uniform secret $z_2\in\mathbb F_p$ and reveal $v_2={z_1}^{-1}\cdot z_2$. We apply lemma 1 with $u={z_1}^{-1}$ (which belongs to $\mathbb F_p^*$), and conclude that revealing $v_2$ reveals nothing about ${z_1}^{-1}$, hence nothing about $z_1$.

Thus the part of the protocol where we compute and reveal $v_2={z_1}^{-1}\cdot z_2$ has revealed nothing about any quantity in the part of the protocol where we compute and reveal $v_1=a\cdot z_1$. If our choice of $a$ was not zero, by lemma 2, that part of the protocol has revealed nothing about $a$. If our choice of $a$ was $0$, $v_1$ will be $0$.

Hence the answer to question 2 is: the protocol reveals precisely whether $a=0$ or not. No other information about $a$ leaks.

With the statement disallowing $z_1=0$ (or if we reject that as having vanishing odds since $p$ is large), it can be shown that no (or vanishingly few) information about $z_1$ in isolation leaks, and that the only (or almost the only) information that leaks about $z_2$ in isolation is whether $z_2=0$ hold.


AES GCM mode and the message is the same as the password In a case of using a password and get AES key using KDF to encrypt the same password (The password and the message is the same), How secure is that algorithm ?

From Wikipedia Key Derivation Function (KDF):

  In cryptography, a key derivation function (KDF) derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function

You have a password $p$, and you are using a KDF $k=KDF(p)$ to derive the key $k$ and then you encrypt the $p$ as $c=E_k(p)$, where $E$ is AES.

There is a problem here. How are you going to remember the $k$, if you keep the $p$, then what is the aim of encrypting it?

If you look at password manager you will see that;

  Password managers typically require a user to generate and remember one "master" password to unlock and access any information stored in their databases.

One of the benefits of KDF is we input to KDF a human rememberable password to generate cryptographic keys.

You have to use some way to store the $k$ if you delete/forget $p$ and input whenever necessary. Also, $k$ is generated what is the aim of encrypting the $p$? Just delete it?

and remember AES-GCM is authenticated encryption mode.


Encryption using two keys Suppose we have two secret keys K1 and K2, I'd like to ask if there is any encryption scheme that allows us to derive another key K12 from K1, and K2 and for a message x, EK12(x) = EK1(EK2(x)).

EK(x) is the encrypted text of x using key K.

Yes, it is possible with a symmetric system.

One way would be if we had a public prime $p$, and secret keys $k_1, k_2$ which are values relatively prime to $p-1$.

And, we define $E_k(M) = M^k \bmod p$; decryption then is $D_k(M) = M^{k^{-1} \bmod p-1} \bmod p$ (the value $k^{-1} \bmod p-1$ is easy to compute, given $k$).

And, for $K_{12} = K_1 \cdot K_2 \bmod p-1$, we have $E_{K_{12}}(M) = E_{K_1}(E_{K_2}(M))$


Information Theoretic Oblivious Transfer? Do we have information theoretic oblivious transfer protocols that are that can not be broken by a computationally unbounded attacker?

It is impossible to achieve (fully) information theoretic oblivious transfer (OT), since OT is complete (and so can compute all functions). Since many (most) functions cannot be securely computed information theoretically with two parties, this means that it's impossible. Having said that, we do have OT protocols that provide information-theoretic security for a corrupted sender and computational security for a corrupted receiver, and other OT protocols that provide information-theoretic security for a corrupted receiver and computational security for a corrupted sender.


Entropy measurement from shuffled cards A standard deck of $52$ shuffled playing cards can be used as a source of randomness.

Assuming cards are not replaced as they're drawn, a full deck of cards provides $225.58$ bits of entropy $- 52!$ combinations $= \log_2(52!)$ bits of entropy.

What is the correct way to calculate the bits of entropy supplied by multiple decks of cards?

For a single deck reshuffled 3 times in a row I would expected $\log_2(52!^3) = 676.74$ bits. But for 3 decks shuffled together, what is the value?

Also, if $N$ cards have been drawn of $X$ decks, how much entropy has been accumulated?

This sounds like a homework question but I'm trying to develop this as a feature in a project - https://github.com/iancoleman/bip39/issues/33


Is there a string that's hash is equal to itself? I was wondering if there's any string that has a hash equal to itself, so that – when using any (none specific) hash function – the hash would be equal to that string?

so that:

hash(x) = x

Note that this is not an assignment or anything. I’m just curious and couldn't find any specific answer or reference. And I’m not sure how to go and prove/disprove that to myself!

I restrict to hash functions $H$ with an output of some fixed size $n\ge1$ bit(s), accepting as input some strings, including all $n$-bit strings; MD5 (resp. SHA-1, SHA-256) is an example of such function for $n=128$ (resp. $n=160$, $n=256$).
Whether there exists a solution to $H(x)=x$ depends on the particular hash function. If $H$ is a random function (as MD5, SHA-1, and SHA-256 aim to be), the answer is YES with odds next to $63.2\%$ for practical values of $n$.
More precisely: $H(x)=x$ can hold only if $x$ has exactly $n$ bits. There are $2^n$ values of $x$ that satisfy the later condition, and restricting $H$ to such $x$ there are $(2^n)^{(2^n)}$ different $H$ functions, of which $(2^n-1)^{(2^n)}$ such that $H(x)=x$ has no solution. Therefore, if we choose one $H$ uniformly randomly, odds are exactly $1-{(2^n-1)^{(2^n)}\over(2^n)^{(2^n)}}=1-(1-2^{-n})^{(2^n)}$ that we picked $H$ such that $H(x)=x$ has a solution. As $n$ increases, this converges very fast to $1-1/e\approx0.632$ (where $e\approx2.718$ is the base of the natural logarithm).
This does not tell if MD5 has the property that there exists a solution to $\operatorname{MD5}(x)=x$ (which would be a 128-bit bitstring $x$). The best we can say is that it likely holds, with odds about to 63%, but determining if the assertion is true or false is beyond our current computing power (the best method we have is exhaustive search, and if the answer is no it would require $2^{128}$ hashes; otherwise it is still likely to require over $2^{126}$ hashes, which is beyond reach).
PHP specific: if md5($string) === $string had some solution, that would be a 32-character string of hexadecimal lowercase characters; we are not hashing the same $2^{128}$ candidates as above so the question is not equivalent, but the reasoning can be adapted, and again the best we can say is that it is likely there's a solution, with odds about 63%.
Further, the original question asked if there is a string such that md5($string) == $string. To answer this, we must take into account how the == operator works in PHP due to type juggling (it holds that "0042" == "42", and "20e2" == "   +002000"). It is overwhelmingly likely that there is a solution (just consider that among the $2^{200}$ strings consisting of 200 space or tab and an additional final 0, we expect about $31\cdot2^{72}$ hash to one of "00000000000000000000000000000000", "000000000000000000000000000000e0" .. "0e000000000000000000000000000000"); however we can't exhibit one.

It is easy to define a hash function $H$ such that $H(x)=x$ has no solution: for example, define
$$H(x)=\begin{cases}x\oplus1&\text{if }\operatorname{MD5}(x)=x\\\operatorname{MD5}(x)&\text{otherwise}\end{cases}$$

It is also easy to define a hash function $H$ such that $H(x)=x$ has at least one solution: for example, choose some arbitrary 128-bit constant like $k=\text{af5d2bc6c9181f76f3161f43f41f6aeb}$, and define
$$H(x)=\begin{cases}k&\text{if }x=k\\\operatorname{MD5}(x)&\text{otherwise}\end{cases}$$

There can be no $x$ such that for all possible hash functions $H$, $H(x)=x$.
Proof by contraposition: assume there is such $x$, a function $H$ with $x$ having that property, and consider the function $\tilde H$ defined by $\tilde H(x)=H(x)\oplus1$.


RSA Attack, known public key and ciphertext. Can decrypt the message m? I'm stuck with this problem: Assume Alice and Bob are using RSA to communicate each other. Given Bob's public key $(217,7)$, Alice send the ciphertext $c=53$ to Bob through RSA encryption. Now, Eve can read the ciphertext $c$, how can Eve decrypt the ciphertext and read plaintext $m$?

Some examples of answers to similar questions:

Theoretical decryption of RSA
https://crypto.stackexchange.com/questions/31433/how-to-decrypt-a-rsa-encrypted-text-file-when-only-public-key-is-known

Hint: $N = 217 =\ ?\ \times\ ?$

In the public key, $e$ is the exponent and $N$ is modulus, therefore $e < N$.
If $m$ is your message, $m^e \mod N = c$ is the cipher.
To decipher you need to find $d$, such as: $d \times e = 1 \mod \phi(N)$.
You will then be able to find $m$: $c^d \mod N = m$


Calculating CP-ABE random secret $s$ initialized by the data owner I am analyzing the Bethencourt CP-ABE model to understand the math behind it. If a data user is able to satisfy the access policy attached to the ciphertext, that user is able to decrypt the encrypted message.

This is made possible because the data user can calculate:

$$e(g,g)^{rq_{x}(0)}$$

We know that:

$$q_{x}(0) = s$$

Where:

$$s \in Z_P$$

Is it in any way possible for the data user to calculate the value of this secret $s$ if he/she can satisfy the access policy or is it made so that the data user can never be able to obtain this value?

Extracting $s$ in this case would seem to be equivalent for the discrete log problem in the bilinear group $\mathbb{G}_0$, using the Bethencourt CP-ABE paper notation.

To see this, first consider that if you can solve DLP in $\mathbb{G}_0$, then obviously you can solve $s$ from the ciphertext component $C=h^s$, as $h$ is already known (part of the public key).

The other direction follows from that if we assume an algorithm $\mathcal A$ capable of extracting $s$, given the global public key $PK$, ciphertext $CT$, and a secret key $SK$ capable of decrypting $CT$ according to the scheme, we can also use this algorithm to compute a discrete logarithm in $\mathbb{G}_0$.

We can use $\mathcal A$ as follows:

First assume that we know, which message, attribute-set and policy-formula $\mathcal A$ is able to "break". Call these $M,S$ and $\mathcal{T}$, respectively.
Assume $\mathcal A$ takes as input a set $\{PK, CT, SK\}$, and outputs $s \in \mathbb{Z}_P$
Now, given $g, g^s \in \mathbb{G}_0$, where $s$ is unknown, and $g$ is a generator of $\mathbb{G}_0$, we can construct $PK=\{g,g^\beta, g^{1/\beta}, e(g,g)^\alpha \}$ simply by passing $g$ as such and selecting $\alpha, \beta \in \mathbb{Z}_P$ randomly, as stated by the scheme. We can also construct $SK=\{g^{(\alpha+r)\beta},\{g^rH(j)^{r_j},g^{r_j}\}_{j \in S}\}$ similarly, as we have already selected $\alpha, \beta$. We also select randomly $r$ and $r_j$ to match $S$.
Constructing $CT$ is trickier, since it involves handling $s$, which is unknown to us, but needs to be conformant to the scheme in the eyes of $\mathcal A$. First part of $CT$ is $\mathcal{T}$, which we simply replace from what we know of $\mathcal A$. The second part is $C^o=Me(g,g)^{\alpha s}$, which we can construct, since we know $g,\alpha, g^s$ and $e(g^\alpha,g^s)=e(g,g)^{\alpha s}$. The third part is $C=h^s = (g^s)^\beta$, again elements we know or have created. The fourth part, $\{C_y,C'_y\}_{j \in S}$ (leaf-node shares in the exponents of both $g$ and the attribute hashes) requires knowing the (secret) shares for $s$. Constructing this depends on the realization that the shares and their polynomials per each node are created randomly, independently of $s$. They are only tied to $s$ by making, for example, $q_{x_1}(0)=q_R(1)$, where $q_R()$ is the polynomial of the root node (and $q_R(0)=s$) and $q_{x_1}()$ is the polynomial for the root's child $x_1$. We can then freely select other polynomial interpolation points randomly and calculate the required $C_y=g^{q_y(0)}$ and $C'_y=H(att(y))^{q_y(0)}$. It doesn't matter that we don't know $s$, as $\mathcal A$ is responsible for the possible decryption, and the interpolation points are selected independently of $s$, even though they are later connected to $s$.


length extension attack on an MD5 hash of a text file of about 10K Bytes? How much computing time on a typical desktop computer would it take to find a new length and new data to extend a text file of about 10K Bytes with a given MD5 hash?

First of all, let us explore what a "length extension attack" is; it might not be exactly what you assumed it was.

Suppose we were given the MD5 hash of a bytestring we'll call $A$; we may have no idea what the string $A$ consists of, but we do know its length.

Then, we can create a bytestring $B$ (which depends on the length of $A$, but not any of its contents; it'll be between 9 and 73 bytes long), so that, for any string $C$ we pick, we can compute the value:

$MD5(A || B || C)$

This value will generally not be the same as the original $MD5(A)$ value; so if you're looking to create second preimages, this doesn't help you.  However, you're looking for (say) a way to attack the use of MD5 as a Message Authentication Code, this might.

As for the time taken to compute the value $B$, and the value $MD5(A || B || C)$, well, that's essentially trivial; $B$ can be computed directly from the length, and the time taken to compute the hash is essentially the time it takes to compute $MD5(C)$.

A number of other hash functions share this observation; SHA-1, SHA-256, SHA-512. There are also other hash functions for which this is not true: SHA-384 and AHS (now known as SHA-3) among them.


CTR mode encryption using PRG In CTR mode encryption, the encryption block is not required to be invertible. Thus, a PRF can be used instead of a PRP. However most of the implementations of CTR mode are based on AES which is a PRP.

This made me think if we can have a PRG as the encryption block where the (key || counter_i) can be supplied as a seed.

If we use a secure PRG such as SALSA20 instead of AES, do we achieve a secure CTR mode encryption?

This will not be secure in general, and is not recommended.  The reason is that a PRG is guaranteed to produce a pseudorandom output only if its input is uniformly random (or pseudorandom).  Moreover, several PRG outputs are jointly pseudorandom only if the PRG is run on independent seeds.  But here you are invoking the PRG on "structured" inputs, i.e., the counter part is known and predictable (hence not (pseudo)random), and the key part is reused multiple times.

Concretely, here is a secure PRG $G$ for which your construction is completely insecure: let $G'$ be a secure PRG, and define $G(s \| \text{ctr}) = G'(s) \| \text{ctr}$, where $\text{ctr}$ has the same length as the counter you use in your construction.  This is still a secure PRG because in proper usage, $s$ and $\text{ctr}$ are uniform and independent.  However, your construction is insecure when instantiated with $G$ because the (public, non-random) $\text{ctr}$ part is simply "passed through" to the output, and the successive calls to $G$ always produce the same $G'(s)$ part.

CTR mode with a PRF is OK because a PRF has the property that even for adversarially chosen inputs (e.g., the counter values), the outputs of the PRF (on the same random secret key) are jointly pseudorandom.