Solved

What algorithm is used to encrypt

Posted on 2014-04-19
33
619 Views
Last Modified: 2014-05-05
Hi All,

I'm trying to work out what encryption algorithm is used for encrypting a password. This is just to develop a tool for accessing the password when the user has forgotten the password.

I will give you a  few examples of the inputs and outputs.

Could someone please point me in the right direction as to whether a known algortithm is used for this ?

Input    -> Output
abcd ->   163138183151
ABCD -> 163138183151
abcdefgh -> 176143145138121130125166
ABCDEFGH -> 176143145138121130125166
abcdefghijkl - > 119141116117134157185155131162
ABCDEFGHIJKL-> 119141116117134157185155131162
1234 ->  115090135103
12345 -> 118128071086078
123456 -> 122088085132094138
1234567 -> 125127091107119075122
12345678- > 128095097090073082077118
123456789-> 132126111135090088109131124
12345pass ->  132126111135090146151190182
abc123 -> 170136133129091135
sean -> 181141181161
Hello -> 173179128142136
seanSeanSEAN- > 137144114127148156179161141157
abcxyz-> 170136133200162206


What I have worked out so far is that it is not case sensitive (you get the same values for uppercase and lowercase words) and each character is represented in a 3 digit code.

Please refer below

ABCD -> 163 138 183 151
ABCDEFGH -> 176 143 145 138 121 130 125 166


Your responses will be greatly appreciated ....
0
Comment
Question by:meperera
  • 13
  • 10
  • 4
  • +2
33 Comments
 
LVL 82

Expert Comment

by:Dave Baldwin
ID: 40011003
You have too much repetition in your scheme.  It is likely fairly easy to break.  Generally you best choice is to use the encryption methods provided by your programming language.  All modern encryption is based on sophisticated mathematical methods.  Here is some more info: http://en.wikipedia.org/wiki/Encryption

The most common procedure these days is to simply reset the password when it is forgotten.  It has the advantage that even the host does not know the users password.
0
 
LVL 26

Expert Comment

by:skullnobrains
ID: 40011035
have you noticed that one out of 3 digits is always a 1 ?
looks like the 1s are not significant and it is actually 2 digits per input caracter

additionally, it is most likely reversible (symetric)

it is quite likely custom made. relatively easy to break but that's probably lot's of work compared to brute force

if you really want to go and break it, the way to go is probably start with one and 2 letter passwords like 'a' 'aa' 'ab' 'ba'
0
 
LVL 32

Expert Comment

by:ste5an
ID: 40011269
Don't store passwords. Only store hashes of it. And offer a possibility to reset the password by your user. Anything else is a security issue per se.
0
 
LVL 26

Expert Comment

by:skullnobrains
ID: 40011303
it's obviously not his code, or he would not be trying to break it.

<off topic>
btw, there are quite a few reasons to actually store passwords rather than hashes, one of them being the possibility to implement proper challenge-response authentication.
</off>
0
 
LVL 26

Expert Comment

by:skullnobrains
ID: 40011306
i think i noticed another interesting particularity that should help with the breaking :

abc123 -> 170136133129091135
abcxyz-> 170136133200162206

apparently, when the passwords are the same length, chains that start identically have encrypted counterparts that also start identically. that could indicate that the length itself is used, or that some rotation algorythm in applied as many times as there are characters
0
 
LVL 32

Expert Comment

by:ste5an
ID: 40011309
@skullnobrains: I slightly disagree. See Challenge–response authentication: Password storage.

Using hashes instead of passwords makes no difference in this kind of usage. But for the rest: it is the better solution. No perfect, but better.
0
 
LVL 26

Expert Comment

by:skullnobrains
ID: 40011313
... in which case the hash is used as the secret instead of the password so knowing the hash gives you the same advantages as knowing the password so it just adds complexity but does not make much of a difference... anyway this is really off-topic but i'm ready to discuss this in a private thread if you want.

--

back to the topic, i was wrong about the non significant 1 since there are also a few 2 which all correspond to letters near the end of the alphabet if i'm not mistaken

next step would be to determine if the same letter at the same position is always coded in the same way when the length is the same. if yes, it should actually be rather easy to break the code
0
 
LVL 26

Expert Comment

by:skullnobrains
ID: 40011316
4	163
6	170
8	176
12	119

Open in new window


above is the table mapping how "a" is encoded when at first position depending on the length of the password. @meperera, if you can complete that table, we may find something that applied the proper number of times on a primary number (likely relative to the ascii code) will produce those numbers, or possibly a big number which modulo 256 gives those

also, regardless the length, the 5 number seem to always be low (often <100)
0
 

Author Comment

by:meperera
ID: 40011441
Hi skullnobrains,

Your logic seems very likely.  I have generated another set of outputs. Hope this confirms your theory.

Thank you everyone for your assistance so far.

a ->                                153
aa ->                               157138
ab ->                               157139
ba ->                               158138
bb ->                               158139
b ->                                 154

a->                                        153
aa ->                                157138
aaa ->                                160168166
aaaa ->                               163137181148
aaaaa ->                          166175117131122
aaaaaa ->                         170135131177138181
aaaaaaa->                        173174137152163118164
aaaaaaaa->                        176142143135117125119159
aaaaaaaaa->                        180173157180134131151172164
aaaaaaaaaa->                         113141164156159138114114148121
aaaaaaaaaaa->                  116180178131113145146127140141
aaaaaaaaaaaa->                  119140114114130152179148123153
0
 
LVL 26

Expert Comment

by:skullnobrains
ID: 40011526
just so that you know, i'm giving information without actually expecting to break the code myself which is likely both far beyond my knowledge and my available time

i'm perplex about the fact that the second group for ab and bb are the same. this might indicate that only the number of total letters and the position of the letter are used in which case chances to break it would rise drastically, or that the letters are treated in some specific predetermined order, or possibly in reverse order. you should be able to devise a series of tests that would answer those questions

i'd also be interested in results for individual c d z xb 4b and a few digits.

it would also be good to know which are the allowed caracters. letters + digits case insensitive would make one pop the number 37 out of their minds
0
 

Author Comment

by:meperera
ID: 40011614
Thanks. No I wasn't at all expecting you to break the code. It's just that it appeared you had identified some pattern.

The values for ab and bb are in fact different.

ab -> 157139
bb -> 158139

I will further test to see which characters are allowed.

Thank you again..
0
 
LVL 26

Expert Comment

by:skullnobrains
ID: 40011666
good. just wanted to make this clear so you did not spend time for something that is most likely prone to fail without knowing.

i was only referring to the second group (ie the one standing for the b) which is why i'm interested in xb and 4b (or mb and 2b, it does not really matter as long as it is distant)
0
 

Author Comment

by:meperera
ID: 40012339
Hi skullnobrains,

Each time a string contains two characters and the second character is b it gives it the value 139.

1b = 109139
2b=110139
4b=112139
mb=169139
xb=180139

I will keep hitting it till I can figure out a pattern and report back.
0
 
LVL 38

Expert Comment

by:Rich Rumble
ID: 40012598
It seems like a simple Vigenère, with each position adding or subtracting values against the initial value of that char.
(0p)
(1p) a = 150 +3
(2p) a = 150 +3 +4 = 157
(3p) a = 150 +3 +4 +3 = 160
(4p) a = 150 +3 +4 +3 +3 = 163
(5p) a = 150 +3 +4 +3 +3 +3 = 166
(6p) a = 150 +3 +4 +3 +3 +3 +4 = 170
(7p) a = 150 +3 +4 +3 +3 +3 +4 +3 = 173
(8p) a = 150 +3 +4 +3 +3 +3 +4 +3 +3 = 176
(9p) a = 150 +3 +4 +3 +3 +3 +4 +3 +3 +4 = 180

Open in new window

(first positions only) a ->            153
aa ->           157
aaa ->          160
aaaa ->         163
aaaaa ->        166
aaaaaa ->       170
aaaaaaa ->      173
aaaaaaaa ->     176
aaaaaaaaa->     180
aaaaaaaaa a ->   113
aaaaaaaaa aa->  116
aaaaaaaaa aaa-> 119
I've added spaces after the 9th position there is an overflow/negative integer occurrence to the first position. Also the first position letters are so far reliably have a distance of 53 between first position and the ASCII/Decimal equivalent.
I don't know for sure, but I suspect "1" by itself  = 102, I used the following logic to draw that conclusion
(4p) a = 150 +3 +4 +3 +3 = 163
1234 ->  115 090 135 103

1 = 115 -3 -4 -3 -3 = 102 1=102
1 = 49 dec/ascii (102-49=53)
a = 97 dec/ascii (150-97=53)
A = 65 dec/ascii (150-65=85) <--- not using Ucase, all passwords are being converted to lcase and given their ascii value, see ORD)

Open in new window

Once I figure out the overflow/negative number the other positions will be easy.
Hopefully gets others on the right track... also "B" in 2nd position does not always equal 139 in the examples above, but should if all positions total are less than 4.
ABCD ->     163 138 183 151
abcdefgh -> 176 143 145 138 121 130 125 166
abcdefghijkl -> 119 141 116 117 134 157 185 155 131 162
-rich
0
 
LVL 26

Expert Comment

by:skullnobrains
ID: 40013425
seems like you spotted something which i'm too tired to fully analyse now. i understand apply a dummy algorythm +3 +4  harcoded and a vigenere afterwards, using ascii codes again. possible and could account for some letters being always low (fith) or high. too lazy to check more tonight.

seems there is something missing though because the range includes a few non-printable characters, or the key is written using random ascii codes ?

--

we can confirm this is somehow based on the ascii codes of the characters

letter, code1of2, ascii_code
4 , 112, 52
a, 157, 97
difference is both 45, and the ascii code of the lower case is used as a basis

--

i'd go for 1 = 105 unless i'm missing something
112 - 3 = 109 would be the 1 in 1x
and 109-4 would be 1
0
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 

Author Comment

by:meperera
ID: 40029215
Hi All,

Sorry about the delay in getting  back. I have been interstate working on another project.

I shall get back to you all as soon as I start working on this in the coming days.

Thank you again..
0
 

Author Comment

by:meperera
ID: 40033683
Just a quick note skullnobrains you were right. The value of 1 is 105.
0
 
LVL 38

Expert Comment

by:Rich Rumble
ID: 40035747
I shouldn't have subtracted the last 3, so yes 105 it should of been :)
It'd be nice to know what can and cannot be used, like Space, tilde or any other special chars that might not be valid. I don't think we need to know, but it would make it complete to know what is and isn't a valid char.
I'll have a look at this again this weekend, the main thing to figure out is what the highest and the lowest single char is, something like 180 to 200 perhaps.
-rich
0
 
LVL 26

Expert Comment

by:skullnobrains
ID: 40036392
actually, we already have enough information to solve the problem completely.
( note that z is 200 and something )

there are a wealth of possible ways to produce this transformation, ranging from a vigenere where the key is picked from a text at various places depending on the password length, to a huge number generated using that same length and then added to the concatenated ascii codes of the input

... but who cares : given the above information, as long as we know a single password with the same length, we can deduce the original input from any given output.

for each letter, we just need to calculate the difference between the encoded string and the reference string, which will reveal the distance between the password and the reference string in terms of ascii code.

might be nice to generate the NULL character password ( - 97 to each 3 digits group in the A table above ) for each password length. then the reverse algorithm can just be coded by substracting the number corresponding to the password length and transforming each group of 3 digits to the letter that has the corresponding ascii code.
0
 
LVL 26

Expert Comment

by:skullnobrains
ID: 40036445
here is a small demonstration code in php

copy-paste any number of passwords and encoded passwords in $REF

<?php

$REF="
abcd ->   163138183151
ABCD -> 163138183151
abcdefgh -> 176143145138121130125166
ABCDEFGH -> 176143145138121130125166
abcdefghijkl - > 119141116117134157185155131162
ABCDEFGHIJKL-> 119141116117134157185155131162
1234 ->  115090135103
12345 -> 118128071086078
123456 -> 122088085132094138
1234567 -> 125127091107119075122
12345678- > 128095097090073082077118
123456789-> 132126111135090088109131124
12345pass ->  132126111135090146151190182
abc123 -> 170136133129091135
sean -> 181141181161
Hello -> 173179128142136
seanSeanSEAN- > 137144114127148156179161141157
abcxyz-> 170136133200162206
";

$REFS=explode("\n", $REF);

$passrefs=array();

foreach($REFS as $R){
	list($k,$p)=explode('->',$R);
	$k=trim($k);
	$passrefs[strlen($k)]=array(
		'pass'=>$k,
		'enc'=>trim($p)
		);
}

//print_r($passrefs);

while($enc=fgets(STDIN)){
	$enc=trim($enc);
	echo "$enc --> ";
	$len=strlen($enc)/3;
	if(!$passref=$passrefs[$len]){
		echo "no ref for length=$len\n";
		continue;
	}
	for($i=0;$i<$len;$i++){
		echo chr(
			ord($passref['pass'][$i])
			-substr($passref['enc'],$i*3,3)
			+substr($enc,$i*3,3)
			);
	}
	print("\n");
}

Open in new window


and here is the result. testing using the A table

$ php /tmp/x.php
176142143135117125119159
176142143135117125119159 --> AAAAAAAA
119140114114130152179148123153
119140114114130152179148123153 --> PHP Notice:  Undefined offset: 10 in /tmp/x.php on line 43
no ref for length=10
173174137152163118164
173174137152163118164 --> aaaaaaa
160168166
160168166 --> PHP Notice:  Undefined offset: 3 in /tmp/x.php on line 43
no ref for length=3
166175117131122
166175117131122 --> Aaaaa

i must admit i don't really know why some A's end up in capital letters and others do not

best regards
0
 

Author Comment

by:meperera
ID: 40037106
Hi skullnobrains .. Thanks for that.  Any chance you could give me the pseudo code for the logic you used because my php is not the greatest ?

Thanks again..
0
 
LVL 38

Expert Comment

by:Rich Rumble
ID: 40037703
This is the duality of security, and how intentions and ulterior motives can never be known on the internet. I wrote about this: Here...

It's a hard call to make, put a stop to the Q and the author may go to another forum, let it continue and we figure out the reverse and then no nuclear launch code is safe.

What if the Q shows up in  another TA, re-worded "Solve my custom puzzle" and some examples are shown, maybe the numbers are fudged (perhaps the OP already added 53 to each) and that TA figures it out. Ulterior motive changed (maybe it's the same?), but the Q is more "innocuous" and would of flown under the radar.

It's a fine line, I'll stop any further work, but many Q's that come up in the Security TA have this duality/risk with them. Especially when it's tools for security testing, auditing or evaluation. The questions look one way, but could be used in another if the true intention is counter to stated intention. When I answer them I'm looking at the helping aspect, helping someone understand something they didn't before so they can positively affect their security posture. This question appealed more to my curious side (another security MUST), and it's solution may be beneficial to the OP only (we still don't know what application this is for, which is why I kept looking at it), which could be good, but the more professional side of me says: "reset passwords, reversing them is never a best practice". Also, use tried and true/tested hashes, salted if possible, something that is not reversible.

-rich
0
 
LVL 38

Expert Comment

by:Rich Rumble
ID: 40038232
Understood, but I think I will stop and instead recommend:
Alerting the vendor (maybe not, could be home-grown) and ask for real encryption/hashing.
Reset the users passwords, in this case they aren't very well protected so reversing and or reusing them might be fine too. :)
-rich
0
 

Author Comment

by:meperera
ID: 40038925
Netminder, if you read the initial question carefully you will understand the explicitly described purpose for identifying the algorithms used.

With Vigenère  algorithm each algorithm is unique depending how many and what keys are used and therefore I don't believe that will be a threat to national security.

I work on these projects because I'm constantly amazed by the combinations of computing and mathematics used by different smart minds.

Therefore I don't understand your need to intervene as this obstructs the purpose of this forum.  The only assumption is that you either did not read or understand the question and the responses.
0
 
LVL 26

Expert Comment

by:skullnobrains
ID: 40038934
hello @netminder

thanks for reminding us about the exact terms of use which will be a good reference in the future. (and are in agreement with my own ideology)

in this specific thread, i considered several facts

- this algorithm is obviously a custom one, so it is very unlikely that providing a way to reverse it will prove that useful to a script kiddie trying to mess with a different implementation

- this kind of algorithms have been reversed decades if not centuries ago and the recipes to break them are all over the internet (and i probably would not be able to do so otherwise )

- the fact that the author can generate passwords for any given string and provide them here seems consistent with his goals. i have little to no reason to doubt him in this specific case.

hence my call was (and still is) to consider this topic legit. if you have reasons to think otherwise, i'll be happy to read them ; they might prove useful in order to spot illegitimate activities later on.

i'll carefully consider the warning, but will proceed to answering the author's question unless instructed otherwise.

best regards.
0
 
LVL 26

Expert Comment

by:skullnobrains
ID: 40038936
@mepera. we cross-posted on that last post. i must admit i'm not very comfortable with what you just wrote : it is uselessly agressive with @netminder, you self-assume the goals of the forum, you give different goals than the ones you gave in the first place, and algorithms do not change when keys change...
0
 

Author Comment

by:meperera
ID: 40038968
@skullnobrains, I respect that you don't agree with my views. However they are my views and not a display aggression towards anybody.

I appreciate your brilliance in guiding me through this equation so far.
0
 
LVL 26

Accepted Solution

by:
skullnobrains earned 500 total points
ID: 40039150
i will not discuss further the usefulness

--

here is a simpler algorithm for you to code

use the a table

a->                                        153
aa ->                                157138
aaa ->                                160168166
...

deduce the table for ascii code 0 (ie null character) for each possible length
(by removing 97 which is ascii code for a from each group)

spaces are here for readability but these are numbers

1 -> 066
2 -> 060 041
3 -> 063 071 069

(beware i'm sticking leading zeros but the number is decimal and not octal)

then the algorithm is simpler : substract the number corresponding to the input length and you're left with the ascii codes of the plain text

for example : bb ->  158139

158139-060041=98098

then each 3 digits group is an ascii code
098 098 -> b b

this should be trivial to code whatever the language as long as it can handle big numbers and you're careful that leading zeros don't make it interpret numbers as octal
0
 

Author Comment

by:meperera
ID: 40041844
@skullnobrains Thank you so much for your brilliance. Your time is greatly appreciated.

Best of luck.
0
 

Author Closing Comment

by:meperera
ID: 40041847
Brilliant... Keep up the great work.
0

Featured Post

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

In this era, as you know, cybercrime and other sorts of frauds using the internet has increased day by day. We should protect our information assets and confidential information from getting exploiting by the attacker or intruders. Most of the fraud…
There are many reasons malware will stay around and continue to grow as a business.  The biggest reason is the expanding customer base.  More than 40% of people who are infected with ransomware, pay the ransom.  That makes ransomware a multi-million…
This demo shows you how to set up the containerized NetScaler CPX with NetScaler Management and Analytics System in a non-routable Mesos/Marathon environment for use with Micro-Services applications.
This video explains how to create simple products associated to Magento configurable product and offers fast way of their generation with Store Manager for Magento tool.

705 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now