How good an encryption algorithm is this?

[Tim Roberts]

Surely XOR requires binary, which was only invented in the1940s or
something?
Why would people before the age of computers understand binary?

Are you serious??? Number bases are a part of mathematics. They have been
used for thousands of years. The Mayans are supposed to have used base 60.
Any society with an inclination towards mathematics probably played with
base 2.

George Boole (for which "Boolean" is named) wrote a book called "The Laws
Of Thought" in 1854. This book introduced what we now know as "Boolean
logic", including rigorous definitions of NEGATION, AND, OR, and XOR.

No, despite the arrogance of most of us in the industry, and contrary to
what the patent office would lead you to believe, the essential truth is
that NOTHING about computers is new.

 

[Bonj]

For now, key exchange needs to be solved on a case-by-case basis (that's
what security consultants derive most of their income from). So, maybe if
you describe the original problem you are trying to solve, rather than
your attempted solution, somebody might be able to help you.

It's pretty much the problem of the key needing to be constantly persisted
in software on the client.

Another person seems to be having exactly the same problem, see:

Google Groups: View Thread "Have you seen what a decompiler can extract
from c# ..."

for a post that has worked through in the groups a lot of the debate I've
been having with myself.

 

[Bonj]

Really! interesting...

Are you serious??? Number bases are a part of mathematics. They have
been
used for thousands of years. The Mayans are supposed to have used base
60.
Any society with an inclination towards mathematics probably played with
base 2.

George Boole (for which "Boolean" is named) wrote a book called "The Laws
Of Thought" in 1854. This book introduced what we now know as "Boolean
logic", including rigorous definitions of NEGATION, AND, OR, and XOR.

No, despite the arrogance of most of us in the industry, and contrary to
what the patent office would lead you to believe, the essential truth is
that NOTHING about computers is new.

 

[Bonj]

Interesting... thanks.

Can you explain to me or point me to any resource which explains what
"salting" is?

 

[Ian Griffiths [C# MVP]]

"Bonj" replied:

Do you reckon that, albeit not the be all and end all, but that if I
achieve that, then it's a big step forward in the right direction?

Only marginally. It's a bare minimum requirement, but it's very easy to
demonstrate algorithms that meet this requirement and yet are still
completely unsecure. So having this property is unfortunately not really a
strong indicator of the quality of the algorithm.

With respect to your particular algorithm, you seem to want actual concrete
proof that it's of no use, so here goes... There's problem with your
algorithm that is related to the problem above.

Even if a given input byte doesn't necessarily produce the same output byte
every time, it's also bad if a given input byte in a given input position
always encrypts to the same output byte. (Indeed these are effectively just
the same problem on different scales.) With a robust encryption system,
changes in one byte position in the input tend to have a much more
widespread effect in the output. Without this property, then all sorts of
attacks become quite simple - you can do the same kind of statistical
analysis that has already been discussed for each byte offset. Obviously
this takes longer than with a simple one byte substitution, but it's still a
major weakness, which is why you'll never see a serious encryption algorithm
that has this problem.

And I'm afraid your code suffers from this problem.

To illustrate why, let me point out something about your approach. You've
actually made your algorithm look a lot more complex than it really is.
Your Encrypt routine really does nothing more than XOR with the same
repeating 256 byte pattern every time. You'll find that if you call your
Encrypt function like this:

BYTE cheat[256];
BYTE zero[256];
ZeroMemory(zero, 256);
Encrypt((_TCHAR*)zero, 256, cheat);

the 'cheat' array will now contain the 256 byte repeating pattern that you
XOR all your input with. You can now just use a much simpler routine:

for (int i = 0; i < dataByteCount; ++i)
{
data ^= cheat[i % 256];
}

This is effectively equivalent to both your Encrypt and Decrypt routine. I
was able to take the byte buffer generated by your Encrypt routine and
recover the original string data this way. And looking at this code it's
very obvious what's being done to the data.

Your code makes it look like you're doing something more complex than you
really are, because you are using a roundabout way of choosing the repeating
256 byte pattern that you XOR the data with - you're deriving it from the
input keys rather than using them directly. But this roundabout derivation
doesn't add any security - cryptanalysis techniques that can be brought to
bear on repeating XOR patterns will work just fine regardless of how the bit
pattern was generated - it's the fact that it repeats that is important.
(Indeed your code might even be less secure than simply XORing against one
of the 256 byte input keys - it is possible that your munging introduces
patterns or statistical artifacts into the bit patterns that could be
exploited to make the attack more efficient.) Data encrypted this way can
be analyzed using exactly the same statistical techniques as can be used
with single byte substitution. It will take a little longer to do, but this
is ultimately a very unsecure encryption system. You would be a whole lot
better off with any of the encryption algorithms offered by the Crypto API.

(Also, a chosen plaintext attack would allow the attacker to get enough
information to decrypt *everything* in just one go. For example, my code
above to generate the 'cheat' block was a chosen plaintext attack, where my
chosen plaintext is all zeroes. But it happens to work for any 256 byte
chosen plaintext. And since you're talking about encrypting people's
passwords, then presumably I get to choose the plaintext - it's my password.
All I need to do is enter a 256 byte password, look at what you encrypt that
to, XOR it with my original password, and I've now got the 256 byte pattern
you're XORing everything with. I can now decrypt any password you encrypt.)

I'm by no means a crypto expert by the way, but it only takes the most basic
understanding of cryptanalysis to know that a simple repeating 256 byte XOR
is easily attacked. I'm afraid I have to agree with everyone who has been
telling you that encryption systems devised by people who don't know
anything about encryption tend to be utterly unsecure. Possibly you don't
believe this yet, because you think that if you keep working at it you'll
get there eventually. And maybe you will, but I'm not sure you'll get there
without learning a lot more about crytpanalysis - pretty much every
successful encryption algorithm has learned from the attacks made on older
algorithms. And if you do this learning, you'll discover just how many
people have tried before you to roll their own brand new systems, only to
fail to come up with anything useful. And you'll also learn why it is that
so many people have told you not to bother trying to roll your own
encryption algorithm...

Of course there may well be utterly novel new ways of doing encryption as
yet undiscovered. But historically, it looks like the odds are against you.
And I still think it's insane to try and invent your own in the hope that
you'll hit upon a new technique rather than relying on tried and tested
techniques.

 

[Ian Griffiths [C# MVP]]

"Bonj" replied:

No, I don't believe this at all. We've already established that the
algorithm itself shouldn't need to be secret, right?
So discovering the *key* that I use for the encryption and decryption is
the only thing that's going to need to be done to crack it, right?

You're missing the point. The problem with your algorithm is that it makes
it relatively easy to discover the key if you simply know how the algorithm
works and you have enough sample encrypted messages to look at.

The fundamental problem with your algorithm is that even if you were to
solve the problem of being able to keep the key secret (which is hard, but
doable), the key wouldn't remain secret for long - your algorithm reveals
information about the key each time it encrypts something. That's a serious
flaw.

*So, how does the CryptoAPI help me protect the secrecy of the key
any better than my own algorithm would?*

Because if you *do* manage to come up with a way of keeping the key secret,
none of these algorithms will destroy your hard work by revealing the key
through the way in which they encrypt data. Unlike your algorithm.

 

[Guest]

But surely there are enough CryptoAPI examples to help you out, aren't

there?

Not that work, no.

True, but I suspect most people who *were* trained in encryption would
have understood the reasons given for not trying to come up with your
own algorithm to start with.

You're contradicting yourself...
What about the people that *have* invented the *good* encryption algorithms?
Were they trained in encryption? If so, then by your principle "they should
have known not to bother trying to invent their own", but if they weren't
trained, then how did they manage to invent a good algorithm? What I take out
of this is that, obviously, *either*, people are wrong in that home grown
algs are not _necessarily_ worse (albeit certainly no better) than
professional ones, OR, you don't actually need to be particularly clever or
trained in cryptography to invent a professional crypto algorithm, just by
fluke - happen to stumble on some tricky principle or something. I suspect
it's the latter though...

That's really not a good argument in favour of creating your own
algorithm. Just because someone hasn't already studied yours in an
attempt to crack it doesn't mean it's more secure than one which many
highly skilled people *have* studied and failed to find significant
problems with. It just means they haven't looked at yours yet.

Mmmm, maybe so. It's not really a good argument in favour of creating my
own, but since a better description of my problem perhaps would be "how to
persist the key on the client in secrecy", then it's not all that strong an
argument against it either.

They crack it when it's worth cracking, rather than now. Do you really
want to only find out whether your algorithm is strong enough when it's
already deployed in the field, and is protecting real-world data?

Again , I would say that I've posted a link to a google groups thread which
is someone else having exactly the same problem, but perhaps described in a
better way than I am capable of (and certainly hammered out quite a lot)!

But why did you wait until you'd made what you could see was a bad
choice before posting, rather than just asking for help with the
CryptoAPI in the first place?

Because I feared people would gloss over the post. At least if I post my own
attempt,
a) I can't be vindicated hitting a brick wall and not trying any further
b) If people thought it was good, then hopefully they would point it out.
c) If people thought my algorithm is bad in itself or a bad idea, they'll be
more keen to point out how to do the CryptoAPI in order to set me on the
right track.

 

[Guest]

Because if you *do* manage to come up with a way of keeping the key secret,

Mmmm... fine. But I don't see that happening....

 

[Alex]

But surely they'd need to understand how to disassemble machine
language into assembly and understand where the "pass" takes place
in order to do that?

No, unless you link with ODBC statically. Against dynamic library one
can just drop proxy DLL on that computer.

Thus wouldn't be able to be done by a layman...
At the end of the day, if Bloke A's rival, Bloke B, were to sneak
onto Bloke A's computer at lunch time, he could technically run
whatever SQL he liked just by starting up my program (that the
password encryption security is a minor part of), and running it
on the server through the application's interface. But, the crux
is, Bloke A would return from lunch, discover Bloke B had done
something, and immediately change his password, and make sure he
locked his terminal in future - the real question is could Bloke B
download a program from the internet, load it onto Bloke A's
computer, point it at the registry and my program's application
directory, and hey presto, he actually *discovers* the password,
to use at his own leisure, from his own computer.

Wouldn't it be easier to just copy the registry entry "as is" and
bring it to his computer? If you're trying to protect against it, you
need, as a minimum, to encrypt using a key unique to the computer
(for example, through the hash of the mac address, or hard drive id)

Alex.

 

[Igor Tandetnik]

It's pretty much the problem of the key needing to be constantly
persisted in software on the client.

Like I said, key exchange is unsolved in the general case. So by
defining the problem in such general terms, you are not going anywhere.

Let's take yet another step back: _why_ do you need the key constantly
persisted in software on the client? What do you need this key for, what
data are you trying to protect, who needs access to this data, how do
you plan to know she is the right person to have access to said data?
What threats do you envision and are trying to protect against?

I highly recommend "Writing Secure Code" by Michael Howard et al [1]. It
has a chapter on storing secrets securely on Windows machine. All of
them essentially boil down to trusting Windows authentication: if the
person managed to log into her Windows account, you assume that she is
indeed who she says she is.

[1] http://www.amazon.com/exec/obidos/tg/detail/-/0735617228
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925

 

[Igor Tandetnik]

Can you explain to me or point me to any resource which explains what
"salting" is?

You may want to read RFC 2898 for an interesting application of crypto
techniques, including salting and stretching (referred to as "iteration
count" in the RFC).

http://www.faqs.org/rfcs/rfc2898.html

If you are really interested in cryptography, do yourself a favor and
get "Applied Cryptography" by Bruce Schneier.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925

 

[RoyFine]

bonj

as we move into definitions, we must be a bit more careful - so i set the
stage first.

consider a database table that has encrypted passwords (not simple xor
mapping encryption, but a one-way hash of the password). if i look at the
encrypted password values, it seems like just so much muddle to me. but in
my spare time, i hash 5 million or so common passwords (in prior spare time,
i wrote a program to generate these) and i save the hashed value with the
plaintext. then i look in your password table, and i just might find a few
values there that are the same as the ones that i computed - if we used the
same algorithm to hash, then i have just discovered a few passwords. this
is a dictionary attack (using my dictionary of plaintext trial passwords and
the corresponding hash)! the literature suggests that with todays computer
power, these sorts of attacks are trivial and you can break an entire
password file of a hundred or so in just minutes.

Enter *Salt* - salt is a random string that is concatenated with the
plaintext passwod before you run it through the hash (one-way) function,
then both the salt and the one way has are stored in the database. if you
are using a system generated guid, then every stored value is now 128 bits
longer. but the dictionary attack just got a lot harder - now i have to
compute the dictionary once for every password/salt combination. now,
instead of minutes to recover the passwords, the time jumps up to a couple
of weeks - see feldmeier and karn, unix security-10 years later, applied
cryptography [pg 52-53] by bruce scheiner, and the following link:
http://groups.google.com/[email protected]&output=gplain

roy

 

[Jon Skeet [C# MVP]]

Not that work, no.

You're saying that none of the examples of using CryptoAPI work? That
sounds unlikely.

You're contradicting yourself...

I don't think so...

What about the people that *have* invented the *good* encryption algorithms?
Were they trained in encryption? If so, then by your principle "they should
have known not to bother trying to invent their own", but if they weren't
trained, then how did they manage to invent a good algorithm?

They were trained (and/or did research) and then were in an appropriate
position to invent their own. They knew better than to bother trying to
invent their own without doing research first.

They may well also have been in a rather different situation to you -
namely inventing a new algorithm due to limitations of previous ones.
Your reason was that you couldn't get the existing algorithms working,
not that the algorithms wouldn't actually do what you wanted.

What I take out of this is that, obviously, *either*, people are
wrong in that home grown algs are not _necessarily_ worse (albeit
certainly no better) than professional ones, OR, you don't actually
need to be particularly clever or trained in cryptography to invent a
professional crypto algorithm, just by fluke - happen to stumble on
some tricky principle or something. I suspect it's the latter
though...

No, I don't believe either of those are true.

Mmmm, maybe so. It's not really a good argument in favour of creating my
own, but since a better description of my problem perhaps would be "how to
persist the key on the client in secrecy", then it's not all that strong an
argument against it either.

I don't think we need any more reasons not to invent your own
algorithm, do we?

Again , I would say that I've posted a link to a google groups thread which
is someone else having exactly the same problem, but perhaps described in a
better way than I am capable of (and certainly hammered out quite a lot)!

From what I remember about the link you posted, the poster wanted to
hard code a private key into his code. That's just a Bad Idea,
regardless of obfuscation.

Because I feared people would gloss over the post. At least if I post my own
attempt,
a) I can't be vindicated hitting a brick wall and not trying any further
b) If people thought it was good, then hopefully they would point it out.
c) If people thought my algorithm is bad in itself or a bad idea, they'll be
more keen to point out how to do the CryptoAPI in order to set me on the
right track.

And you didn't think it was worth even asking before wasting your time
coming up with a different algorithm? I could understand if you'd
asked, providing a complete program which wasn't working for you, but
to just *assume* that you wouldn't get an answer seems a bit odd.

 

[Igor Tandetnik]

consider a database table that has encrypted passwords (not simple xor
mapping encryption, but a one-way hash of the password). if i look
at the encrypted password values, it seems like just so much muddle
to me. but in my spare time, i hash 5 million or so common passwords
(in prior spare time, i wrote a program to generate these) and i save
the hashed value with the plaintext. then i look in your password
table, and i just might find a few values there that are the same as
the ones that i computed - if we used the same algorithm to hash,
then i have just discovered a few passwords. this is a dictionary
attack (using my dictionary of plaintext trial passwords and the
corresponding hash)! the literature suggests that with todays
computer power, these sorts of attacks are trivial and you can break
an entire password file of a hundred or so in just minutes.

Enter *Salt* - salt is a random string that is concatenated with the
plaintext passwod before you run it through the hash (one-way)
function, then both the salt and the one way has are stored in the
database. if you are using a system generated guid, then every
stored value is now 128 bits longer. but the dictionary attack just
got a lot harder - now i have to compute the dictionary once for
every password/salt combination. now, instead of minutes to recover
the passwords, the time jumps up to a couple of weeks - see feldmeier
and karn, unix security-10 years later, applied cryptography [pg
52-53] by bruce scheiner, and the following link:
http://groups.google.com/[email protected]&output=gplain

To make dictionary attack even more difficult, you can use stretching
(aka iteration) - instead of just calculating the hash once, you iterate
it 2^N times for some N. Iterate means you calculate the hash of the
password+salt, then the hash of that hash, then the hash of last hash
and so on. The point of the exercise is as follows: when you verify the
password, you need to perform this iteration only once. Suppose it takes
you a second to do that - not too terrible for the user to wait.
However, the attacker perapring the dictionary must do the iteration for
each password/salt combination, and those seconds start to add up. If
the unsalted password could be attacked in minutes, salted one in weeks,
then for salted and stretched it might take years or decades.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925

 

[Simon Trew]

Carl -
Is the comparison of the encrypted data with *actual* random noise the
beginning of one of the techniques used for cracking the encryption?
If so, how does it progress?
(see also reply to Steve Friedl)

More the case that a statistical analysis of the sets of data would produce
much the same results as a statistical analysis of "noise". I guess you
could feed the data into tools that analyse the efficacy of 'random' number
generators, for example.

With many algorithms, of course, you can mathematically prove certain
properties about the output (given certain inputs), so you don't need
necessarily to run empirical analyses.

 

[Ian Griffiths [C# MVP]]

Mmmm... fine. But I don't see that happening....

There are lots of situations in which an attacker might be able to get
access to the encrypted data when they can't get access to the key itself.
So while you obviously can't keep the key secret from *everyone* (the
entities encrypting and decrypting data need to know it, obviously) there
are nonetheless typically individuals who can only see the encrypted data,
and who will not have access to the key.

If in your particular scenario absolutely everyone involved can always see
the keys, then you really may as well not bother doing encryption. (Or at
least don't bother wasting any effort, since the best you'll ever be able to
do is obfuscation - the strength of the encryption is now irrelevant, so you
may as well do whatever is simplest.) But although key management is hard
it's not impossible. It's impossible to solve in general, but there are
many scenarios in which it can be done. (Otherwise nobody would bother with
encryption.)

For example, if I want to send data from my laptop to my server at home,
then it's relatively straightforward for me to make sure that the key is not
known by anyone other than those two computers. I can create a key, put it
on my server and my laptop while I'm at home - I can do this with a USB key
or a disk to make sure that it never goes over my network, meaning that as
long as my machines haven't been compromised, I can be pretty confident that
the key remains a secret shared only by these two machines. And now that
I'm on the road in a different country from my server, I can use that key to
encrypt data sent between my laptop and server over an untrusted network.
(Indeed this is more or less exactly what I'm doing right now - I have a VPN
connection to my home network that is using this very technique.)

If I used your algorithm to encrypt the data, I needn't have bothered taking
these steps to keep the key a secret, because your algorithm would allow
anyone snooping on my traffic to discover the key fairly quickly. I'm
sending several megabytes of data every day, which should be more than
enough for a successful statistical attack on your algorithm.

Fortunately I'm not using your algorithm. So my key has a good chance of
remaining secret. (Of course there are still risks in my key management -
perhaps one of the two machine that know the key has been compromised and
the key stolen, and I've not realised this yet. Or maybe I forgot to delete
the file from my USB disk and someone has got hold of a copy that way. But
there's nothing intrinsic to the design of the system that means the key
will definitely be known to any other party - by design the key remains
secret unless there has been a failure elsewhere.)


By simple saying "I don't see that happening" w.r.t. keeping the key secret,
you are effectivley saying that you are now assuming the key will be known
to all your attackers. If that really is the case for your scenario, then
I'd recommend not bothering with encryption. If you simply start from the
assumption that the key is always public knowledge, then that's not a useful
baseline for judging the usefulness of an encryption algorithm, because
you'll inevitably come to the conclusion that they are all completely
useless.


I'm still not quite sure exactly what it is you're trying to achieve here.
It sounds like you might be attempting to store credentials for connecting
to a SQL Server database in a way that stops people from just reading the
raw connection string and using those credentials for their own purposes,
but I'm not really sure if that's what you're doing. If that is what you
are doing, there are a few well-known solutions to this problem that work a
whole lot better than the approach you are trying to use. (The two obvious
ones being integrated security - not using a SQL username and password at
all - and the DPAPI, which is a technology built into Windows that is
designed to solve pretty much exactly this problem.)

 

[Guest]

How would I make sure that I am linking with odbc statically?

I think I am, but want to make sure of it.
What is the DLL called that the proxy replaces, so I can make sure my app
doesn't depend on it?

Thanks!

 

[Guest]

That's a possibility. I'd not like to use the processor ID because someone
could legitimately upgrade their processor and be rightly confused when they
had to login again. But the hard-drive ID - they would have to set most
things up again then.

 

[Guest]

I might end up using that actually. At the end of the day, if the windows
user account can have SQL security resting on top of it, then it can have my
app's security resting on top of it aswell - and my app's security is only
really remembering the SQL password so they don't have to type it in again
every time anyway for environments where windows authentication isn't
available. So that will probably be satisfactory.

 

[Guest]

And you didn't think it was worth even asking before wasting your time

coming up with a different algorithm?

Yes, I did ask. It was called "CryptoAPI uniqueness" and is a bit further
down than this thread. Nobody bothered replying.