|
Science Forum Index » Cryptography Forum » Back Doors
Page 1 of 1
|
| Author |
Message |
| mike3 |
 Posted: Sat Dec 20, 2003 2:40 am |
|
|
|
Guest
|
Hi.
How can one implement "back doors" in an encryption algorithm that
would allow someone to decode all messages encrypted with it provided
they know some secret "magic" formula? Is this a very diffcult problem
or an easy one?
Just curious. |
|
|
| Back to top |
|
| Douglas A. Gwyn |
| Posted: Sat Dec 20, 2003 3:15 am |
|
|
|
Guest
|
"mike3" <mike4ty4@yahoo.com> wrote in message
news:1d54b7e4.0312192340.3f693332@posting.google.com...
Quote: How can one implement "back doors" in an encryption algorithm that
would allow someone to decode all messages encrypted with it provided
they know some secret "magic" formula? Is this a very diffcult problem
or an easy one?
It's neither, or both.
Back doors are simple enough in "toy" implementations, for example
HELLO => QHSETLZLPO
More typical block cipher systems that don't expand the message size
would have to use more subtle means. Note that a sufficiently "weak"
(crackable) system can be considered to have a "back door", since all
one has to do is crack that easy-to-crack system. For example, if the
system hashes the key to, say, 8 bits and uses the result as the real key,
if it uses an inherently strong block encryptor the ciphertext will look
quite random, but it takes at most 2^8 = 256 trial decryptions to
recover the ciphertext! |
|
|
| Back to top |
|
| Michael Amling |
| Posted: Sat Dec 20, 2003 11:45 am |
|
|
|
Guest
|
mike3 wrote:
Quote: How can one implement "back doors" in an encryption algorithm that
would allow someone to decode all messages encrypted with it provided
they know some secret "magic" formula? Is this a very diffcult problem
or an easy one?
One way would be to replace the random number generator used to
select encryption keys with MD5("mike3's secret back door" ||
CurrentTime()).
--Mike Amling |
|
|
| Back to top |
|
| Foo Bar |
| Posted: Sat Dec 20, 2003 12:21 pm |
|
|
|
Guest
|
mike4ty4@yahoo.com (mike3) writes:
Quote: Hi.
How can one implement "back doors" in an encryption algorithm that
would allow someone to decode all messages encrypted with it provided
they know some secret "magic" formula? Is this a very diffcult problem
or an easy one?
Depends on what the requirements are on the trapdoor. For example, how
hard should it be to detect? Rijmen and Preneel suggested one way of
designing hard-to-detect trapdoors into a cipher in "A family of
trapdoor ciphers" (FSE'97) [1], but that proposal was broken by Wu, Bao,
Deng and Ye in "Cryptanalysis on Rijmen-Preneel Trapdoor Ciphers"
(Asiacrypt '9 [2].
Note that a block cipher with a trapdoor that is hard to detect but easy
to use can be used for public key encryption.
Perhaps the Weis and Lucks paper "'All your key bit are belong to us'
the truth about black box cryptography" [3] contains something
interesting.
[1] http://www.esat.kuleuven.ac.be/~cosicart/ps/VR-9703.ps.gz
[2] http://icsd.i2r.a-star.edu.sg/publications/WuHongjun_1998_trapdoor.pdf
[3] http://www.nluug.nl/events/sane2002/papers/WeisLucksAllYourKeybit.ps
/FB
--
Foo Bar (foobar965@hotmail.com) |
|
|
| Back to top |
|
| John Savard |
| Posted: Sat Dec 20, 2003 12:57 pm |
|
|
|
Guest
|
On Sat, 20 Dec 2003 02:15:00 -0600, "Douglas A. Gwyn"
<DAGwyn@null.net> wrote, in part:
Quote: "mike3" <mike4ty4@yahoo.com> wrote in message
news:1d54b7e4.0312192340.3f693332@posting.google.com...
How can one implement "back doors" in an encryption algorithm that
would allow someone to decode all messages encrypted with it provided
they know some secret "magic" formula? Is this a very diffcult problem
or an easy one?
It's neither, or both.
Back doors are simple enough in "toy" implementations, for example
HELLO => QHSETLZLPO
More typical block cipher systems that don't expand the message size
would have to use more subtle means. Note that a sufficiently "weak"
(crackable) system can be considered to have a "back door", since all
one has to do is crack that easy-to-crack system. For example, if the
system hashes the key to, say, 8 bits and uses the result as the real key,
if it uses an inherently strong block encryptor the ciphertext will look
quite random, but it takes at most 2^8 = 256 trial decryptions to
recover the ciphertext!
Incidentally, I discuss this subject on my web page at
http://home.ecn.ab.ca/~jsavard/crypto/mi060706.htm
where I consider how one might make a cipher program easy to validate,
so that it would be hard to put an undetectable back door in it.
Basically, I propose excluding all randomness from the program's
operation, requiring the user to put random padding at the end of
messages manually if required.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html |
|
|
| Back to top |
|
| John A. Malley |
| Posted: Sat Dec 20, 2003 5:12 pm |
|
|
|
Guest
|
mike3 wrote:
Quote: Hi.
How can one implement "back doors" in an encryption algorithm that
would allow someone to decode all messages encrypted with it provided
they know some secret "magic" formula? Is this a very diffcult problem
or an easy one?
Just curious.
Here's a thought inspired by some recent reading on the connection
between steganography and secure computing:
Use a side channel to leak information about the key while the cipher is
in use. Deliberately design in (one or more) seemingly innocuous
behaviors that your implementation modulates to signal an external
receiver.
What's hard is selecting the behavior to modulate, determining how to
modulate the behavior in a way that won't attract attention
(dynamically, while running on user system, and statically, when subject
to code reviews with the safe assumption of open-source code
distribution), and how to measure the modulation remotely and without
attracting attention.
That's a bare-bones answer, there's a lot more to think through here. I
regret not giving a specific example, but in theory this should be
possible, and would be specific to an implementation.
John A. Malley
102667.2235@compuserve.com |
|
|
| Back to top |
|
| CryptWolf |
| Posted: Sat Dec 20, 2003 7:20 pm |
|
|
|
Guest
|
"mike3" <mike4ty4@yahoo.com> wrote in message
Quote: news:1d54b7e4.0312192340.3f693332@posting.google.com...
Hi.
How can one implement "back doors" in an encryption algorithm that
would allow someone to decode all messages encrypted with it provided
they know some secret "magic" formula? Is this a very diffcult problem
or an easy one?
Design into the system a master key. Every file is then readable using
the master key or the user key. Note that this is an obvious solution.
It is generally easiest to implemented using a public key system so
that security is not compromised if carefully designed. No private keys
need to be embedded. This would be typical in a corporate environment
where management might want a way to recover anything the
employees might encrypt. The weakness is the master private key
becomes the prime target. Otherwise well known algorithms may be
used and a very secure system can be designed.
If you assume the enemy knows everything about the system,
hidden key, key leaking or key weakening schemes fail instantly.
All just forms of obscurity.
Hard or easy depends on what you actually have to work with.
Note that it doesn't prevent someone from downloading an
alternative without a back door.
CryptWolf |
|
|
| Back to top |
|
| Bryan Olson |
| Posted: Sun Dec 21, 2003 2:40 am |
|
|
|
Guest
|
mike3 wrote:
Quote: How can one implement "back doors" in an encryption algorithm that
would allow someone to decode all messages encrypted with it provided
they know some secret "magic" formula? Is this a very diffcult problem
or an easy one?
A back door must not be exploitable by others who know the
cipher spec (otherwise it becomes a front door). If you can
create such a back door, you can also create a public-key
cipher; the sender makes up a key, encrypts a suitably redundant
message, throws away the key and send sends the ciphertext.
Also, given a public key cipher, you can create a back-door
cipher (though the existence of the back-door may be too
obvious). The sender encrypts the message with the real key
and also with a fixed public key.
I was not the first to observe a rough equivalence between
public-key ciphers and ciphers with back doors. Matt Blaze
might have been.
--
--Bryan |
|
|
| Back to top |
|
| Scott Contini |
| Posted: Sun Dec 21, 2003 6:10 pm |
|
|
|
Guest
|
mike4ty4@yahoo.com (mike3) wrote in message news:<1d54b7e4.0312192340.3f693332@posting.google.com>...
Quote: Hi.
How can one implement "back doors" in an encryption algorithm that
would allow someone to decode all messages encrypted with it provided
they know some secret "magic" formula? Is this a very diffcult problem
or an easy one?
Just curious.
Have a look at:
http://www.hpl.hp.com/techreports/1999/HPL-1999-12R1.pdf
Scott |
|
|
| Back to top |
|
| mike3 |
| Posted: Sun Dec 21, 2003 10:43 pm |
|
|
|
Guest
|
"CryptWolf" <RWilliams01nospam@no.spam.sceinet.no.spam.com> wrote in message news:<d95fdc915bf9777ecd86061f7da3ca87@news.teranews.com>...
Quote: "mike3" <mike4ty4@yahoo.com> wrote in message
news:1d54b7e4.0312192340.3f693332@posting.google.com...
Hi.
How can one implement "back doors" in an encryption algorithm that
would allow someone to decode all messages encrypted with it provided
they know some secret "magic" formula? Is this a very diffcult problem
or an easy one?
Design into the system a master key. Every file is then readable using
the master key or the user key. Note that this is an obvious solution.
It is generally easiest to implemented using a public key system so
that security is not compromised if carefully designed. No private keys
need to be embedded. This would be typical in a corporate environment
where management might want a way to recover anything the
employees might encrypt. The weakness is the master private key
becomes the prime target. Otherwise well known algorithms may be
used and a very secure system can be designed.
If you assume the enemy knows everything about the system,
hidden key, key leaking or key weakening schemes fail instantly.
All just forms of obscurity.
Hard or easy depends on what you actually have to work with.
Note that it doesn't prevent someone from downloading an
alternative without a back door.
CryptWolf
Here's the "conventional" method of applying a public key algorithm:
Encryption:
1. Make a random symmetric key.
2. Encrypt that with public key.
3. Use random key to encrypt main message with fast symmetric algorithm.
4. Send encrypted random key and encrypted message together.
Decryption:
1. Decrypt random symmetric key with private key.
2. Use recovered key to decrypt main message.
Would this work as a good back door?:
Encryption:
1. Make a random symmetric key.
2. Encrypt that with public key.
3. Encrypt a second copy with the "master" hardwired internal public key.
4. Use random key to encrypt main message with fast symmetric algorithm.
5. Send both copies of encrypted random key and encrypted message together.
Decryption (with recipient's private key)
1. Decrypt user key-encryped symmetric key with recipient's private key.
2. Use recovered key to decrypt main message.
Decryption (with master private key)
1. Decrypt master key-encryped symmetric key with recipient's private key.
2. Use recovered key to decrypt main message.
Would that make a good back door (as long as it is not mentioned)? |
|
|
| Back to top |
|
| CF |
| Posted: Thu Dec 25, 2003 9:40 pm |
|
|
|
Guest
|
"mike3" <mike4ty4@yahoo.com> wrote in message
news:1d54b7e4.0312211943.8eb983d@posting.google.com...
Quote: "CryptWolf" <RWilliams01nospam@no.spam.sceinet.no.spam.com> wrote in
message news:<d95fdc915bf9777ecd86061f7da3ca87@news.teranews.com>...
"mike3" <mike4ty4@yahoo.com> wrote in message
news:1d54b7e4.0312192340.3f693332@posting.google.com...
Hi.
How can one implement "back doors" in an encryption algorithm that
would allow someone to decode all messages encrypted with it provided
they know some secret "magic" formula? Is this a very diffcult problem
or an easy one?
Design into the system a master key. Every file is then readable using
the master key or the user key. Note that this is an obvious solution.
It is generally easiest to implemented using a public key system so
that security is not compromised if carefully designed. No private keys
need to be embedded. This would be typical in a corporate environment
where management might want a way to recover anything the
employees might encrypt. The weakness is the master private key
becomes the prime target. Otherwise well known algorithms may be
used and a very secure system can be designed.
If you assume the enemy knows everything about the system,
hidden key, key leaking or key weakening schemes fail instantly.
All just forms of obscurity.
Hard or easy depends on what you actually have to work with.
Note that it doesn't prevent someone from downloading an
alternative without a back door.
CryptWolf
Here's the "conventional" method of applying a public key algorithm:
Encryption:
1. Make a random symmetric key.
2. Encrypt that with public key.
3. Use random key to encrypt main message with fast symmetric algorithm.
4. Send encrypted random key and encrypted message together.
Decryption:
1. Decrypt random symmetric key with private key.
2. Use recovered key to decrypt main message.
Would this work as a good back door?:
Encryption:
1. Make a random symmetric key.
2. Encrypt that with public key.
3. Encrypt a second copy with the "master" hardwired internal public key.
4. Use random key to encrypt main message with fast symmetric algorithm.
5. Send both copies of encrypted random key and encrypted message
together.
Decryption (with recipient's private key)
1. Decrypt user key-encryped symmetric key with recipient's private key.
2. Use recovered key to decrypt main message.
Decryption (with master private key)
1. Decrypt master key-encryped symmetric key with recipient's private key.
2. Use recovered key to decrypt main message.
Would that make a good back door (as long as it is not mentioned)?
Hi mike3,
First off:
1. Encrypt message with public key.
2. Decrypt message with private key. Private key works.
3. Try decrypting message with all other possible keys. If any other key
decrypts message, you know there is a backdoor.
Thus if a master key exists, it can be proven. Just a note in case you're
paranoid and want to take the time and resources to ease your mind.
If your "magic formula" is something other than a master key, your algorithm
or source code may look fishy. Even if your algorithm is complex enough to
fool the worlds smartest, there are still potential problems. Lets take a
look at what this might look like, with no "master key" backdoors.
Let F() be your encryption algorithm.
Let P be your plaintext.
Let k be your public key.
Let Ck be your cyphertext encrypted with key k
Let F(P,k) denote the application of F() on P with k.
F(P,k)=Ck
Let G() be your decryption algorithm.
Le r be your private key.
Let G(Ck,r) denote the application of G() on Ck with r.
G(Ck,r)=P
Then let M() be your "magic function" such that:
M(Ck,k)=P
All you need to do make sure that:
G(Ck,r)=M(Ck,k)
Since, presumably, you already know k and have intercepted Ck, you're all
set.
-KryptoPhalkon
It feels great to post again, after all these years. : ) |
|
|
| Back to top |
|
| David Eather |
| Posted: Fri Dec 26, 2003 9:55 am |
|
|
|
Guest
|
I read a paper by the creators of AES - it was on certain patterns in large
S-Boxes that formed trap doors and allowed for easy decryptions.
"Scott Contini" <contini@matmail.com> wrote in message
news:6f35025c.0312211510.3844ce31@posting.google.com...
Quote: mike4ty4@yahoo.com (mike3) wrote in message
news:<1d54b7e4.0312192340.3f693332@posting.google.com>...
Hi.
How can one implement "back doors" in an encryption algorithm that
would allow someone to decode all messages encrypted with it provided
they know some secret "magic" formula? Is this a very diffcult problem
or an easy one?
Just curious.
Have a look at:
http://www.hpl.hp.com/techreports/1999/HPL-1999-12R1.pdf
Scott |
|
|
| Back to top |
|
| Tom St Denis |
| Posted: Fri Dec 26, 2003 10:18 am |
|
|
|
Guest
|
"David Eather" <eather@tpg.com.au> wrote in message
news:3fec4be9@dnews.tpgi.com.au...
Quote: I read a paper by the creators of AES - it was on certain patterns in
large
S-Boxes that formed trap doors and allowed for easy decryptions.
Yes. I don't recall the name of the paper but the jist was you embed linear
weaknesses in the sbox. You make the sbox big enough so they're hard to
find [even with a fast transform].
Now I give the sboxes out [my public key]. People then encrypt a message
[plus say huge known headers] and throw away the symmetric key. I [who
knows the linear weakness] can now apply a linear attack to the ciphertext
given. Since there are a lot of known plaintext/ciphertexts the attack can
work [not always].
The scheme is totally impractical but was neat nonetheless.
Tom |
|
|
| Back to top |
|
| Foo Bar |
| Posted: Fri Dec 26, 2003 3:46 pm |
|
|
|
Guest
|
"Tom St Denis" <tomstdenis@iahu.ca> writes:
Quote: "David Eather" <eather@tpg.com.au> wrote in message
news:3fec4be9@dnews.tpgi.com.au...
I read a paper by the creators of AES - it was on certain patterns in
large
S-Boxes that formed trap doors and allowed for easy decryptions.
Yes. I don't recall the name of the paper but the jist was you embed linear
weaknesses in the sbox. You make the sbox big enough so they're hard to
find [even with a fast transform].
I gave a reference to that paper in my post to this thread with message
id <fy%Eb.39217$mU6.142195@newsb.telia.net>.
<SNIP>
Quote: The scheme is totally impractical but was neat nonetheless.
And broken.
/FB
--
Foo Bar (foobar965@hotmail.com) |
|
|
| Back to top |
|
| |
