How the ECDSA algorithm works

Posted on by

To popular demand, I have decided to try and explain how the ECDSA algorithm works. I’ve been struggling a bit to understand it properly and while I found a lot of documentation about it, I haven’t really found any “ECDSA for newbies” anywhere. So I thought it would be good to explain in simple terms how it works so others can learn from my research. I have found some websites that explain the basic principles but nowhere near enough to actually understand it, others that explains things without any basics, making it incomprehensible, and others that go way too deep into the the mathematics behind it.

ECDSA stands for “Elliptic Curve Digital Signature Algorithm”, it’s used to create a digital signature of data (a file for example) in order to allow you to verify its authenticity without compromising its security. Think of it like a real signature, you can recognize someone’s signature, but you can’t forge it without others knowing. The ECDSA algorithm is basically all about mathematics.. so I think it’s important to start by saying : “hey kids, don’t slack off at school, listen to your teachers, that stuff might be useful for you some day!” 🙂 But these maths are fairly complicated, so while I’ll try to vulgarize it and make it understandable for non technical people, you will still probably need some knowledge in mathematics to understand it properly. I will do this in two parts, one that is a sort of high level explanation about how it works, and another where I dig deeper into its inner workings to complete your understanding. Note however that I’ve just recently learned this stuff, so I’m definitely not an expert on the matter.

So the principle is simple, you have a mathematical equation which draws a curve on a graph, and you choose a random point on that curve and consider that your point of origin. Then you generate a random number, this is your private key, you do some magical mathematical equation using that random number and that “point of origin” and you get a second point on the curve, that’s your public key. When you want to sign a file, you will use this private key (the random number) with a hash of the file (a unique number to represent the file) into a magical equation and that will give you your signature. The signature itself is divided into two parts, called R and S. In order to verify that the signature is correct, you only need the public key (that point on the curve that was generated using the private key) and you put that into another magical equation with one part of the signature (S), and if it was signed correctly using the the private key, it will give you the other part of the signature (R). So to make it short, a signature consists of two numbers, R and S, and you use a private key to generate R and S, and if a mathematical equation using the public key and S gives you R, then the signature is valid. There is no way to know the private key or to create a signature using only the public key.

Alright, now for the more in depth understanding, I suggest you take an aspirin right now as this might hurt! 😛

Let’s start with the basics (which may be boring for people who know about it, but is mandatory for those who don’t) : ECDSA uses only integer mathematics, there are no floating points (this means possible values are 1, 2, 3, etc.. but not 1.5..),  also, the range of the numbers is bound by how many bits are used in the signature (more bits means higher numbers, means more security as it becomes harder to ‘guess’ the critical numbers used in the equation), as you should know, computers use ‘bits’ to represent data, a bit is a ‘digit’ in binary notation (0 and 1) and 8 bits represent one byte. Every time you add one bit, the maximum number that can be represented doubles, with 4 bits you can represent values 0 to 15 (for a total of 16 possible values), with 5 bits, you can represent 32 values, with 6 bits, you can represent 64 values, etc.. one byte (8 bits) can represent 256 values, and 32 bits can represent 4294967296 values (4 Giga).. Usually ECDSA will use 160 bits total, so that makes… well, a very huge number with 49 digits in it…

ECDSA is used with a SHA1 cryptographic hash of the message to sign (the file). A hash is simply another mathematical equation that you apply on every byte of data which will give you a number that is unique to your data. Like for example, the sum of the values of all bytes may be considered a very dumb hash function. So if anything changes in the message (the file) then the hash will be completely different. In the case of the SHA1 hash algorithm, it will always be 20 bytes (160 bits). It’s very useful to validate that a file has not been modified or corrupted, you get the 20 bytes hash for a file of any size, and you can easily recalculate that hash to make sure it matches. What ECDSA signs is actually that hash, so if the data changes, the hash changes, and the signature isn’t valid anymore.

Now, how does it work? Well Elliptic Curve cryptography is based on an equation of the form :

y^2 = (x^3 + a * x + b) mod p

First thing you notice is that there is a modulo and that the ‘y‘ is a square. This means that for any x coordinate, you will have two values of y and that the curve is symmetric on the X axis. The modulo is a prime number and makes sure that all the values are within our range of 160 bits and it allows the use of “modular square root” and “modular multiplicative inverse” mathematics which make calculating stuff easier (I think). Since we have a modulo (p) , it means that the possible values of y^2 are between  0 and p-1, which gives us p total possible values. However, since we are dealing with integers, only a smaller subset of those values will be a “perfect square” (the square value of two integers), which gives us N possible points on the curve where N < p (N being the number of perfect squares between 0 and p). Since each x will yield two points (positive and negative values of the square-root of y^2), this means that there are N/2 possible ‘x‘ coordinates that are valid and that give a point on the curve. So this elliptic curve has a finite number of points on it, and it’s all because of the integer calculations and the modulus. Another thing you need to know about Elliptic curves, is the notion of “point addition“. It is defined as adding one point P to another point Q will lead to a point S such that if you draw a line from P to Q, it will intersect the curve on a third point R which is the negative value of S (remember that the curve is symmetric on the X axis). In this case, we define R = -S to represent the symmetrical point of R on the X axis. This is easier to illustrate with an image : So you can see a curve of the form y^2 = x^3 + ax + b (where a = -4 and b = 0), which is symmetric on the X axis, and where P+Q is the symmetrical point through X of the point R which is the third intersection of a line going from P to Q. In the same manner, if you do P + P,  it will be the symmetrical point of R which is the intersection of the line that is a tangent to the point P.. And P + P + P is the addition between the resulting point of P+P with the point P since P + P + P can be written as (P+P) + P.. This defines the “point multiplication” where k*P is the addition of the point P to itself k times… here are two examples showing this :  

Here, you can see two elliptic curves, and a point P from which you draw the tangent, it intersects the curve with a third point, and its symmetric point it 2P, then from there, you draw a line from 2P and P and it will intersect the curve, and the symmetrical point is 3P. etc… you can keep doing that for the point multiplication. You can also already guess why you need to take the symmetric point of R when doing the addition, otherwise, multiple additions of the same point will always give the same line and the same three intersections.

One particularity of this point multiplication is that if you have a point R = k*P, where you know R and you know P, there is no way to find out what the value of ‘k‘ is. Since there is no point subtraction or point division, you cannot just resolve k = R/P. Also, since you could be doing millions of  point additions, you will just end up on another point on the curve, and you’d have no way of knowing “how” you got there. You can’t reverse this operation, and you can’t find the value ‘k‘ which was multiplied with your point P to give you the resulting point R.

This thing where you can’t find the multiplicand even when you know the original and destination points is the whole basis of the security behind the ECDSA algorithm, and the principle is called a “trap door function“.

Now that we’ve handled the “basics”, let’s talk about the actual ECDSA signature algorithm. For ECDSA, you first need to know your curve parameters, those are a, b, p, N and G. You already know that ‘a‘ and ‘b‘ are the parameters of the curve function (y^2 = x^3 + ax + b), that ‘p‘ is the prime modulus,  and that ‘N‘ is the number of points of the curve, but there is also ‘G‘ that is needed for ECDSA, and it represents a ‘reference point’ or a point of origin if you prefer. Those curve parameters are important and without knowing them, you obviously can’t sign or verify a signature. Yes, verifying a signature isn’t just about knowing the public key, you also need to know the curve parameters for which this public key is derived from.

So first of all, you will have a private and a public key.. the private key is a random number (of 20 bytes) that is generated, and the public key is a point on the curve generated from the point multiplication of G with the private key. We set ‘dA‘ as the private key (random number) and ‘Qa‘ as the public key (a point), so we have : Qa = dA * G (where G is the point of reference in the curve parameters).

So how do you sign a file/message ? First, you need to know that the signature is 40 bytes and is represented by two values of 20 bytes each, the first one is called R and the second one is called S.. so the pair (R, S) together is your ECDSA signature.. now here’s how you can create those two values in order to sign a file.. first you must generate a random value ‘k‘ (of 20 byes), and use point multiplication to calculate the point P=k*G. That point’s x value will represent ‘R‘. Since the point on the curve P is represented by its (x, y) coordinates (each being 20 bytes long), you only need the ‘x‘ value (20 bytes) for the signature, and that value will be called ‘R‘. Now all you need is the ‘S‘ value.

To calculate S, you must make a SHA1 hash of the message, this gives you a 20 bytes value that you will consider as a very huge integer number and we’ll call it ‘z‘. Now you can calculate S using the equation :

S = k^-1 (z + dA * R) mod p

Note here the k^-1 which is the ‘modular multiplicative inverse‘ of k… it’s basically the inverse of k, but since we are dealing with integer numbers, then that’s not possible, so it’s a number such that (k^-1 * k ) mod p is equal to 1. And again, I remind you that k is the random number used to generate R, z is the hash of the message to sign, dA is the private key and R is the x coordinate of k*G (where G is the point of origin of the curve parameters).

Now that you have your signature, you want to verify it, it’s also quite simple, and you only need the public key (and curve parameters of course) to do that. You use this equation to calculate a point P :

P=  S^-1*z*G + S^-1 * R * Qa

If the x coordinate of the point P is equal to R, that means that the signature is valid, otherwise it’s not.

Pretty simple, huh? now let’s see why and how… and this is going to require some mathematics to verify :

We have :

P = S^-1*z*G + S^-1 * R *Qa

but Qa = dA*G, so:

P = S^-1*z*G + S^-1 * R * dA*G = S^-1 (z + dA* R) * G

But the x coordinate of P must match R and R is the x coordinate of k * G, which means that :

k*G = S^-1 (z + dA * R) *G

we can simplify by removing G which gives us :

k = S^-1(z + dA * R)

by inverting k and S, we get :

S = k^-1 (z + dA *R)

and that is the equation used to generate the signature.. so it matches, and that is the reason why you can verify the signature with it.

You can note that you need both ‘k‘ (random number) and ‘dA‘ (the private key) in order to calculate S, but you only need R and Qa (public key) to validate the signature. And since R=k*G and Qa = dA*G and because of the trap door function in the ECDSA point multiplication (explained above), we cannot calculate dA or k from knowing Qa and R, this makes the ECDSA algorithm secure, there is no way of finding the private keys, and there is no way of faking a signature without knowing the private key.

The ECDSA algorithm is used everywhere and has not been cracked and it is a vital part of most of today’s security.

Now I’ll discuss on how and why the ECDSA signatures that Sony  used in the PS3 were faulty and how it allowed us to gain access to their private key.

So you remember the equations needed to generate a signature.. R = k*G and S= k^-1(z + dA*R) mod p.. well this equation’s strength is in the fact that you have one equation with two unknowns (k and dA) so there is no way to determine either one of those. However, the security of the algorithm is based on its implementation and it’s important to make sure that ‘k‘ is randomly generated and that there is no way that someone can guess, calculate, or use a timing attack or any other type of attack in order to find the random value ‘k‘. But Sony made a huge mistake in their implementation, they used the same value for ‘k‘ everywhere, which means that if you have two signatures, both with the same k, then they will both have the same R value, and it means that you can calculate k using two S signatures of two files with hashes z and z’ and signatures S and S’ respectively :

S – S’ = k^-1 (z + dA*R) – k^-1 (z’ + da*R) = k^-1 (z + da*R – z’ -dA*R) = k^-1 (z – z’)

So : k = (z – z’) / (S – S’)

Once you know k, then the equation  for S because one equation with one unknown and is then easily resolved for dA :

dA = (S*k – z) / R

Once you know the private key dA, you can now sign your files and the PS3 will recognize it as an authentic file signed by Sony. This is why it’s important to make sure that the random number used for generating the signature is actually “cryptographically random”.  This is also the reason why it is impossible to have a custom firmware above 3.56, simply because since the 3.56 version, Sony have fixed their ECDSA algorithm implementation and used new keys for which it is impossible to find the private key.. if there was a way to find that key, then the security of every computer, website, system may be compromised since a lot of systems are relying on ECDSA for their security, and it is impossible to crack.

Finally! I hope this makes the whole algorithm clearer to many of you.. I know that this is still very complicated and hard to understand. I usually try to make things easy to understand for non technical people, but this algorithm is too complex to be able to explain in any simpler terms. After all that’s why I prefer to call it the MFET algorithm (Mathematics For Extra Terrestrials) 🙂

But if you are a developer or a mathematician or someone interested in learning about this because you want to help or simple gain knowledge, then I’m sure that this contains enough information for you to get started or to at least understand the concept behind this unknown beast called “ECDSA”.

That being said, I’d like to thank a few people who helped me understand all of this, one particularly who wishes to remain anonymous, as well as the many wikipedia pages I linked to throughout this article, and Avi Kak thanks to his paper explaining the mathematics behind ECDSA, and from which I have taken those graph images aboves.

P.s: In this article, I used ’20 bytes’ in my text to talk about the ECDSA signature because that’s what is usually used as it matches the SHA1 hash size of 20 bytes and that’s what the PS3 security uses, but the algorithm itself can be used with any size of numbers. There may be other inaccuracies in this article, but like I said, I’m not an expert, I just barely learned all of this in the past week.

158 thoughts on “How the ECDSA algorithm works”

  5. oh my god my mind and my head are hurting now :s Good Luck with the new fix that all i can say bro 😀

  6. I wish I could contribute some how, I love math. Taking calc 2 in college right now, but damn man. I’m still cleaning brain chunks off my wall from my head exploding after reading this

  8. So now you concede defeat.
    Will you at least apologize for how you treated me when I tried to TELL you what you would face?

    Banning people for having sense? God, is the PS3 “scene” that insane?

    • I don’t concede defeat, and no I won’t apologize for how I “treated” you… The issue is not that you told me “the trap door function is impossible to reverse”, it’s the fact that you insulted me in every way possible, ignoring everything I said. I don’t feel like repeating myself, but for the last time :
      sony failed with the ecdsa implementation, not once, but twice, I never said “WE WILL FIND THE KEY”, I said “there is a chance that we will find a collisions if that specific signature was created using that faulty implementation”. We’re still not sure yet if it was done using that faulty implementation or not. You told me what I COULD face, not what I WOULD face.. and I told you that I KNEW, *but* there was incertainty in whether or not they screwed up their random number generator in their implementation because we have samples, we have proof to show that their second implementation that signs stuff with the exact SAME CURVE (different key though) had multiple collisions because of a poor PRNG. And for stating that, and not accepting your comments about how we are wasting our time, you started insulting me.. that is what caused you to be banned, nothing else.

  9. In your previous article you remarked that Sony had implemented a backup key checking mechanism, in this article you indicate it as being fixed. Which is it ? (From what I understand they could not fix it, so they must be using a backup method.)

    Also would it not be possible to write some software to detect a key collision – that even the average joe could use ? Basically it could assume the random numbers are the same on two different signed packages then it would see if a third key could be accepted by the private key reverse enginereed by the other two. So everyone could upload a signature and the software would run this test against all the other signatures.

    Nz

    • Yeah, it’s not really a “backup key checking mechanism” but basically the NPDRM file has two signatures, the first one had the faulty implementation so we got the private key, but the second one doesn’t.. so we can sign part of the file, but we can’t sign the whole npdrm file for that second signature.
      As for the collision detection, that was the plan when I said “we’ll need the help of the community”, there is (I think) still a plan for a homebrew app that would collect signatures from the ps3 files and send them to a server to try and see if there is a collision.

      • But this does mean that all the old games had a second valid signature as well, right? Otherwise, it wouldn’t work on new firmware…? So every official app and disc can be checked for the random collision, yes? Even if it’s a launch disc?

        • yes, exactly. and hopefully there’s an ecdsa fail on older games… however, game discs don’t use NPDRM, so it’s actually just for psn games/demos, even launch versions…

          • Gotcha… discs won’t use NPDRM, only PSN games… and this means that all homebrew is actually technically disguised as PSN content to work properly, yes?

          • I think I’m starting to follow it all. Thanks for the update/explanation. So, one last curiosity (unless you spark more), if it’s used to sign everything except disks, and disks are only signed using the first signature, why don’t we make everything we home-brew boot off a disk instead? I mean, we know new games work on old firmware (sans a bit of patching), can this not be done? Or are disks encrypted using the non-faulty key system?

          • You’re welcome.
            And no, we can’t make homebrew boot off a disc simply because the ps3 would need to authenticate the disc as an original.. just like backups can’t run from a burned disc, homebrew can’t run from a burned disc. however, you did get that right, the plan is to make the ps3 believe somehow that the game is from a disc even if it’s not.. or to find a way to make it boot the SELF even if it’s not npdrm… stuff like that.. that’s the “new exploit” we need to find now.. so new research has started.

          • Yes! I’m starting to understand! Go me!

            And thanks for all the hard work!

            BTW… not sure if this helps… but there is an authentic 3.74 pup that came out with the FF 13-2 disk. I didn’t even see it on wiki yet. Not sure, but would you like a copy to examine…?

            Maybe there’s somethin’ special in it…?

      • Thanks for clarifications, intriguing idea (below) about making the ps3 think the app is running off a disk. That will take a trick or two, but it would be an awesome soft mod…

  11. It may be easier to first understand why the DSA algorithm works for general groups. Often it is explained for integers modulo a prime which is ok.

    Separately (and optionally), learn how elliptic curve points may form a group.

    Finally, apply DSA over the latter, fancier underlying group to get ECDSA!

  12. Thanks for clearin this up a bit… So… if I read it properly, the “random integer” *must* be a prime to work properly… kind of what I was wondering on your last post when I was saying to find the largest prime number, stick it in for an integer, and look for a non-repeating pattern, right…?

    • no, the random number doesn’t need to be a prime, it’s just a random number which is used in the point multiplication.. what needs to be prime numbers is the modulo and (possibly, not sure yet), the curve parameters

  13. @kakaroto this is a hell of a write.

    I hope that everyone is appreciative of what you’re doing.

    Thanks for all your hard work.

  16. Thank you for this write up. I had a vague understanding of how this all worked and your explanation helped me bring it all together. I won’t say I’m an expert on the matter now, but I think I understand it enough anyway.

    My area of interest is really with the firmware update process. Any system on 3.55 or lower is able to install even the 4.00 update. This means it’s possible to hijack the update process, bypass certain checks and include some code of our own.

  17. Few! only read half of it. I’ll continue after my brain cools down.
    Need to find meanings of some of those math terms in my language.

    Ps:-Your teaching skills are really GOOD!
    Kakaroto you should start hacking tutorials for dummies in this site. So we’ll be able to hack devises too.

  18. Thanks KaKaRoTo, keep the good working, hope you’ll find with your friends what is missing to the 4.00 HEN.

    Salam alikoum

  19. whooh. i hope now shitheads realize that making a jailbreak isnt a piece of cake. hats off to u kakaratos. eventough i m not really looking forward for a ps3 jailbreak, i appreciate your work uptill now. respect
    From Pakistan

  21. Great job on the explanation. I enjoyed reading, and hope for more like it. My brain needs a rest now.

  22. Thanks Kakaroto for this article. That was an interesting read.

    As far as I understand, homebrews can no longer run on 3.56+ FW because Sony now checks whether the second ECDSA signature is valid and we don’t know how to calculate it as we don’t have the private key. But there is something I still don’t understand: since we can pack and sign FWs that can be installed from 3.55 (that’s how we make 3.55 MFWs right?), why can’t we take the 4.0 PUP, unpack it, locate where the ECDSA signature check is performed, patch it to bypass it, and then pack and sign the firmware again to be able to install it from 3.55? Then there would be no need to know the ECDSA private key right?

    • Exactly, you understood it correctly.
      The reason for not being able to pack/sign a 4.0 PUP that is modified to ignore the checks is because those checks are now hidden inside lv0, which noone is able to decrypt so far. so we can’t decrypt the firmware as long as we can’t decrypt lv0.
      But yes, you are right, if we have the keys for lv0, then we would just skip the ecdsa checks and wouldn’t need the private key for it.

      • Even if the checks are inside lv0, we can obviously already get around these checks in currents CFWs. What’s stopping us from hacking apart new firmwares so lv0 isn’t updated?

        • not just the checks, the encryption keys too, everything got hidden there, so without decrypting lv0, you can’t decrypt the rest of the firmware (which uses new keys), so even if you don’t update lv0, it just means you won’t be able to decrypt the new firmware, so the ps3 can’t run it without the latest lv0 version.

          • Ok, so follow me here. In order to install the new lv0, it would need to be decrypted. As we don’t have the keys to do this, I can only assume that this decryption is done by the currently installed lv0. Otherwise we’d be able to find the keys within the stuff we already can decrypt. I suppose this depends on how tightly lv0 stuff is insulated from the rest of the system, but is there any way you could hijack lv0 to get the results of that decryption, even if you can’t get the key itself? Maybe you could even decipher the key using a side channel attack involving feeding the decryption algorithm data you control and measuring the electromagnetic activity to see how the CPU is dealing with it. I’m not sure, I really don’t know enough about the cell to say for sure if this stuff is feasible, but it seems like your time would be much better served trying to attack lv0 than messing with ECDSA. Even if you were able to find another vulnerability with how the PS3 handles it’s signatures, Sony would just patch it and send us back to square one. Crack lv0 on the other hand, and the PS3 is ours forever.

          • No, lv0 is decrypted by the bootldr which is not updateable and is on the NOR/NAND and is itself encrypted with a per console key. See here : http://ps3devwiki.com/wiki/Boot_Order
            Also, even if you could decrypt it or dump it from RAM after it was decrypted, it still won’t help because you wouldn’t be able to modify and re-encrypt it.. if you can’t modify it, you can’t tell it to ignore/bypass the ecdsa signatures.
            ALSO, the issue is not with lv0, simply because like I said, my HEN is for official firmwares, I have no way of modifying the firmware, even if I wanted to.. so even if I had all the lv0 keys and everything, it wouldn’t apply to the HEN.

          • I was thinking more you should just give up on the HEN and try to crack the PS3 more thoroughly. If you could get the lv0 of new firmwares decrypted, you could get the keys to decrypt the rest of the stuff and then re-encrypt it with the 3.55 keys to make a hybrid firmware with the old lv0. Seems useful to me.

          • some are working on that, but it would still be useless if you’re not on 3.55 already or if you don’t have a flasher.. and for those, there is already a solution (3.55 cfw), so I don’t care so much about it. I actually want to bring a software-only solution to those who already updated to 4.0 and in this case cracking lv0 is useless

  23. BOOM!!!

    I have no idea what you have just written man. I stopped reading just after the Aspirin point! Good luck with this man. Hope you succeed but if not i’m not in any worse position than i currently am!

  24. Yep..This is all linear algebra, modulo random numbers, being a math major this is not foreign to me. But how the hell do you implement the math into code? Tell me because I want to start modeling this

    • MIT or Cambridge should offer a prize to anyone who can break the ECDSA in general, just to prove its robustness

      • I think there is already a prize to anyone that breaks it.. I’m not sure, but I know that there are some mathematical problems that are unsolved and there is a 1 million $ prize to those who can solve it. I can’t remember the name of the association handling this stuff.
        As for code implementing it, look at ‘ec.c’ of fail0verflow’s ps3tools.
        Read that Lecture14 from Avi Kak, it explains how you can do the math for doing the additions..
        (derive the function to get the tangeant or whatever, or for two points, the slope is of the form ax + b, where the slope is y1-y2/x1-x2, etc… then all sorts of math to give a final huge function to calculate the point addition based on the x/y of the two points).

        • 1 million dollars to hack a gaming console? wow. all this effort and all this time to run homebrew and play apps. is this really all worth it? i can understand if it was going to have backup but you said you have no intention on having anything to do with piracy.

          • no, not 1 million $ to hack a gaming console, it’s 1 million $ to prove mathematical theorems or find solutions to unsolved mathematical problems that no one could solve. It’s called the Millenium Prize Problems. see here : http://en.wikipedia.org/wiki/Millennium_Prize_Problems
            As for ECDSA, it’s not part of those 7 mathematical problems, but I’m sure that there is some other group handing out similar prizes for solving things like that, but of course, it’s impossible :p

    • When i read the article, the first thing that came into my mind is Linear Algebra. There is no way to solve this by having only Calculus knowledge.

      I would like to thank Bbd for raising this point (it’s good to see people with knowledge trying to help rather than spamming “OMG when you release the CFM?”) and also Kakaroto for sharing this problem to us.

      Cheers man and keep up the good work. Lets hope you’ll find someone with an advance knowledge on this subject to help you solve this mystery out.

  25. I am new to this so is each file in the firmware signed individually or is the firmware signed as a package? I have some other ideas but need this answer first.

    • firmware itself is signed, then in it are files that are signed and encrypted, once decrypted, they are packed into other files that are signed and encrypted, then once decrypted, you get the actual firmware files.. which are themselves SELF files which are signed and encrypted…

      • So in 3.56+ firmware is each level of signing and encryption using the same keys or is their a new random interger and a new hash algorithm for each level of signing and encryption down to the file level?

          • Thank you for the synopsis and replying to my questions. Many people would not be so kind as to help someone not at their level of understanding. My head hurts at the moment from trying to digest all of this information. I am wondering though if there is any help we can get from using polar coordinates system based mathematics for elipses vs. cartesian coordinate system mathematics. I am not well studied on polar coordinate mathematics .

          • You’re welcome.
            I’m not well studied on math in general (this is the first mathematics I’ve done or seen in the past 10 years, hehe), so I don’t know what to answer you about that! But what I do know is that cracking the ECDSA algorithm itself is not a task that we’ll be able to do simply because some real geniuses have not been able to find a crack in it, so it’s not newbies like us who will :p You’re free to give it a try though, just for fun 🙂

          • To notimportant: Changing coordinate systems will not help you, no matter if you worked in polar and used trig functions. This isn’t engineering, this is cryptography.

            To kak: for someone who hasnt seen math like this in 10 years you’ve done an excellent job of describing the problem and the theory behind it. Really well done

          • @Bbd: hehe thanks, but it did give me some headaches.. and like I said, I had someone guide me through it which helped me understand all of this.. that’s also the reason I blogged about it, because I’m sure there are others out there who like me need/want to learn it but don’t have someone to guide them through the theory behind it (and wikipedia just isn’t enough).

  26. KaKaRoToKS <3 . Thanks for hard work that you doing , Italy loves you .
    Love from italy

  28. Btw,Kakarotoks, how do u think when ps vita comes out in eu/us maybe there will be some tricks to crack ps3?

    • the trick is to not buy the VITA until Sony relents on their closed proprietary structures. If no one buys VITA it will teach them to release open platforms or people wont support them.

  29. ok ! i read from the top to the end including comments ! U ARE GENIUS ! and MAD ! (in a good way !)

    Good job and Remember ! ” Nothing is Unbreakable !!!! ”

    ….. oh god …. my brain ….. my brainnnnnn

  31. Is it really impossible to have a custom firmware above 3.55?
    I mean, using that collision method you said b4 … if, by any chance, your team manage to get this private key… will it still be impossible to modify the firmware?
    you saying we gotta stay on cfw 3.55 forever? sorry, i’m not criticizing you…no way !
    I just don’t understand all this difficult language…

  32. Ok, so what you are working on will atleast allow us to downgrade from 3.56+ if not provide a 4.00 CFW right..?

  33. i love your work, i want every second, everyday for a “quick” update, i think this is a jump forward because you now know how to calculate the keys etc.

    unfortunately iam not pro at math 🙁 but it looks cool!

    Thanx, we ALL appreciate your work, from you and your team,!

  34. BRAVO ! Kakaroto
    My brain are such a cabbage right now.

    P.S. SELL PS3 and buy XBOX360, this is the only hope…

  35. was a nice read, hope you can find an exploit or a fault on PS3’s ECDSA.
    By the way, there’s no real way to make a “random number”, so could the solution of the security problem be hidden in finding how random the k value is to estimate it’s calculation?

    • Yeah, usually it’s a pseudo random number, but for this kind of stuff, you must use a “cryptographically random” number, and that makes it really random as it has sensors plugged into the PC and takes into account the temperature, wind speed/direction, pressure, sounds, etc… to generate truly random (non predictable) numbers.
      That ‘k’ value could also be created by doing an HMAC SHA1 on the data using the private key.. this way you can’t recreate it without knowing the private key, that’s secure enough.

  36. wow..i can plot graph but definitely cannot read this algorithm, to many variables there.Good job kakaroto^^, it is very nice although i want to know more about it.My mathematic in computer course still not finish learning it.Haha..k keep the good work^^

  37. Hey Kakarotto great explanation!
    I don’t remember much about SHA-1, but maybe a way to exploit it is to find a collision in the hash since every hash is reduced to 20 bits there is a probability for collision, i know the chance is near 0 but we’ve seen them f-up in the past. Still I dunno if we have access to the hashes or just the signed packages. Haven’t put much thought into it but i’m curious if something like this could be useful and has been looked into.
    Regards!

    • SHA1 can have collisions but it’s impossible to predict, and it will take just as long (brute forcing) to find a sha1 collision than it would be to find the private ecdsa key.
      and of course you have the sha1 hash of the message, otherwise you can’t verify if the signature is correct.

      • Hey KaKaRoTo, would it be possible to create a ‘folding’ like application so we could distribute the workload of calculating hashes? That is something I would be very interested in helping to develop.

        • It is possible still dunno how much time it would take it’s also possible to brute force the whole encryption system, i supposse that’s what was done in the link below by dude.
          Since the principle behind encryption is that the security need not be perfect but that the time and resources needed to break it are far greater than the value of the information protected, so it acts as a deterrent. In this case value can be a function of time meaning for ex. if you hack sony’s servers today and find the specs for the ps4 that info could be quite valuable but if the time needed to hack it means you get the info after the official announcement then that info is worthless. Still a brute force method could work maybe raising some cash and using the amazon cloud i’ve read about a guy who found a way to hack wpa-psk networks in minutes with the amazon cloud’s power.

          Sorry for the wall of text lol
          Kakaroto would you mind pointing me in the right direction to start working on ps3 hacking i’ve read some of the wiki’s articles and understand most of it (i’m a computer engineer) but i can’t seem to find which way should i start looking, or maybe if you need a hand on your projects i could be of assistance. Anything is appreciated.

          Regards!

  39. But maybe better tutorial for debuging ps3 on retail ps3’s? Finding some exploitable vuln. in picture/video/music… file then just put our code to work! After that we can search more deeper 😀 Today seem’s, everyone try’s only break signing and encryption stuff !
    But you give me nice overview on this stuff 😀 Thanks a lot!

  40. that’s good man but i think you should use matlab maybe it can help you 🙂 good luck

  41. hey found your name on Google..
    hope that you are KaKaRoToKS 🙂

    I found this info on Wiki
    thought it could be useful:

    On March 29th, 2011, two researchers published a IACR paper[4] demonstrating that it is possible to retrieve a TLS private key of a server using OpenSSL that authenticates with Elliptic Curves DSA over a binary field via a timing attack[5]. The vulnerability was fixed in OpenSSL 1.0.0e

    http://en.wikipedia.org/wiki/Elliptic_Curve_DSA

    Good luck further

    • That was due to a timing attack, which means it was able to “guess” the random number used because it know exactly how it was generated (based on the current time).

      • Actually technically, it CAN be 4… or more to the point 00000000000000000004 [HEX]

        Or… it could be FFFFFFFFFFFFFFFFFFFF [2^160 in HEX]

        OR… pretty much anything in between…

  46. i think my brain just shut down for a bit after seeing this hahaha
    i just had to comment just to say keep up the good work and thank you . and one thing. are you enjoying doing things like this?. things like this make me instrested once i know it 🙂

  47. Too bad us layman cannot help with some sort of BOINC-style attack…?

    You be a cool experiment non-the less! 🙂

  48. hi
    its very nice and important for who waiting to release cfw and congratulation to you for research to have basic knowledge and i hope other people who read the scientific post above and can help to solve the mat…soon contact you.
    thank you

    • No offense Itachi_UCHICHA, thanks for the kind words, but you’ve been spamming the comments of the blog, so I decided to remove your posts, I hope you won’t take it the wrong way.
      Also, if you comment in the future, please refrain from using any word that might be racially offensive to people… and limit yourself to one comment please.
      Thank you.

      p.s: I know about the “acid cfw” and it has nothing to do with this, if you didn’t understand all that I explained in this post about ECDSA, then you probably don’t understand the challenge here.

Comments are closed.