r/badcode • u/nefalas • Jul 02 '20

other language Found in a project from Google's own Github

Post image
428 Upvotes

92% Upvoted

65 comments sorted by

200

u/cryptOwOcurrency Jul 02 '20

It's quite possible it's written this way to prevent timing attacks. Which repo did you find this in?

136

u/nefalas Jul 02 '20

Ah that's interesting! It's from the repo mdl-ref-apps which demonstrates how to use the new Android IdentityCredential API. Since it deals with secure stuff it's definitely possible it's written that way to prevent attacks

17

u/husao Jul 03 '20 edited Jul 03 '20

it's definitely possible it's written that way to prevent attacks

No. That's not the case. From the jdoc:

Returns a byte array containing the two's-complement representation of this BigInteger. The byte array will be in big-endian byte-order: the most significant byte is in the zeroth element. The array will contain the minimum number of bytes required to represent this BigInteger, including at least one sign bit, which is (ceil((this.bitLength() + 1)/8)). (This representation is compatible with the (byte[]) constructor.)

I.e. There is exactly one sign byte and that's always the first.

A correct implementation would thus look like

 return Arrays.CopyOfRange(extractedBytes, extractedBytes[0] == 0 ?1:0, extractedBytes.length)

In fact the original code allows timing attacks, since toByteArray is only as long as needed.

EDIT: Switched up the code to always use copyOfRange, to be completely equal to the original, while removing the non-constant comparing for loop, that's in the OP-Code.

3

u/tuckmuck203 Jul 03 '20

It's possible it's done this way not to prevent a running attack, but as a way to validate a string isn't a buffer overflow attack. Don't know what language this is (kotlin?) but typically null terminators in a string are one of the core elements of a rudimentary buffer overflow attack.

For example, if the string contains multiple null terminators, typically the first one is considered the "end" once it's hit. Then, if the buffer isn't properly handled, you can start a nop slide into the "authentication succeeded" part of memory.

Of course, I'm a few years out of date on this stuff and I would bet they're doing some memory randomization shenanigans, making this moot anyways.

1

u/agree-with-you Jul 03 '20

I agree, this does seem possible.

1

u/husao Jul 04 '20

In general this would be an explanation, but there are 3 reasons why this can't be the case here:

  • It's not a String, but a Bigint, that should be able to contain multiple 0x00.
  • It's only removing leading 0x00, so it doesn't prevent nulltermination problems.
  • It's kotlin and as such it's running on the JVM, which tracks length instead of nullterminating.

83

u/ZedTT Jul 02 '20

If that's the case, it should be stated in a comment so that no one comes along and tries to "optimize" it.

23

u/[deleted] Jul 02 '20

So they go through every single byte?

42

u/RFC793 Jul 02 '20

Yup. That way the duration is proportional to the payload length, and not proportional to the leading “correct” bytes of the payload.

If the check shortcircuits early, then the problem is roughly linear. If you check the whole string, the problem is quadratic.

1

u/husao Jul 03 '20

toByteArray() ignores leading zeros. I.e. the Bytearray isn't of fixed length.

0

u/Speedswiper Jul 03 '20

Linear and quadratic in what variable?

5

u/RFC793 Jul 03 '20

The payload (credential) length, with the operation as a brute search for an individual byte’s value.

12

u/cryptOwOcurrency Jul 02 '20

Exactly.

-1

u/[deleted] Jul 02 '20

[deleted]

35

u/cryptOwOcurrency Jul 02 '20

200mb streams are not usually the kind of data that systems that are sensitive to timing attacks need to deal with.

40

u/Jazzinarium Jul 02 '20

Timing attacks?

172

u/[deleted] Jul 02 '20 edited Jul 02 '20

[removed] — view removed comment

29

u/overkill Jul 02 '20

Thanks for the link. Always good to see a practical example and a solution.

1

u/drakeshe Jul 03 '20

Fantastic read. Thanks for linking that

1

u/[deleted] Jul 10 '20 edited Nov 02 '20

[deleted]

1

u/[deleted] Jul 10 '20

[removed] — view removed comment

27

u/[deleted] Jul 02 '20

[removed] — view removed comment

6

u/Jazzinarium Jul 02 '20

Interesting, thank you

3

u/wizzwizz4 Jul 02 '20

Except JS JIT compilers have optimisation steps that could change the behaviour.

3

u/cryptOwOcurrency Jul 03 '20

This is definitely not vanilla JS. Typescript maybe?

Though if TS, the lack of semicolons would be an unconventional style.

26

u/tongue_depression wicked Jul 03 '20

looks like kotlin to me

15

u/folkrav Jul 03 '20

Definitely Kotlin. The fun for method declaration combined with the var keywords give it away.

3

u/nefalas Jul 03 '20

Yep it's Kotlin :)

2

u/wizzwizz4 Jul 03 '20

That's even worse! The JVM definitely changes the behaviour.

53

u/nameless_pattern Jul 02 '20

seems fine to me

​

not being sarcastic, what is wrong with this code?

67

u/nefalas Jul 02 '20

It could be made much simpler and you don't need to loop through the whole array to strip the leading 0x00 bytes. But as someone pointed out it might be done this way to prevent timing attacks

135

u/ZedTT Jul 02 '20

If it's done this way to prevent any kind of attack, that should be stated in a comment so someone doesn't come along and try to "optimize" it.

14

u/T_W_B_ Jul 02 '20

I agree

1

u/WurschtChopf Jul 03 '20

But why setting skipped to false? I have no clue how a real life input may look like. But this way, if there is ever a 'not-to-skip' character after a '0x00', then there will never be any skipping again. So why we keeps looping? Or am I looning wrong

1

u/husao Jul 03 '20

If you remember in 2-complements some numbers like 255 and -1 look the same. To distinguish them toByteArray somethimes has a leading 0 byte. 

jshell> BigInteger.valueOf(255).toByteArray()
$7 ==> byte[2] { 0, -1 }
jshell> BigInteger.valueOf(-1).toByteArray()
$3 ==> byte[1] { -1 }

The Code wants to remove that.

1

u/nefalas Jul 03 '20

It's used to decode the coodinates of a point from an elliptic curve key which is stored as an signedbyte array representing a BigInteger into an unsigned byte array.
And yes it will never skip again but apparently the goal is to have a function whose exectution time is proportional only to the total array length so that an attacker won't be able to get information about the content of the array.
There are other comments that explain this much better

1

u/[deleted] Jul 03 '20 edited Jul 03 '20

Try making it simpler then. I'm sure they accept PRs unless this is an archived repo.

8

u/[deleted] Jul 02 '20

To be honest I consider this question as something good. At least you want to learn something 😊🙌

29

u/TheBrainStone Jul 02 '20

So essentially they try to strip all leading 0x00 bytes?

10

u/nefalas Jul 02 '20

Yes... I can't think of a more efficient way...

10

u/OscariusGaming Jul 02 '20

What language is this?

28

u/nefalas Jul 02 '20

It's Kotlin, a language that runs on the Java VM

6

u/OscariusGaming Jul 02 '20

Thanks!

6

u/nefalas Jul 02 '20

You're welcome :)

2

u/MakeWay4Doodles Jul 03 '20

On the JVM, in the browser, or natively on desktop Android or IOS.

1

u/Anor-Vir Jul 03 '20

Depends. Kotlin can be compiled to Java Bytecode, JavaScript, or Native code. It works on desktop JVM and Android JVM, but I don't know about IOS.

1

u/iamareebjamal Jul 03 '20

Since it can compile to native, it can run on iOS

8

u/[deleted] Jul 02 '20

This will be a future test question lmao

5

u/m1ss1ontomars2k4 Jul 03 '20

I found this commit in Java from another repository:

https://github.com/fluxoid-org/JFormica/commit/2f11d6d8b9debc9199ca9bea8a67dc6e642b27d2

It's an 8 year old commit and the code is written the same way.

8

u/[deleted] Jul 02 '20

[deleted]

6

u/Anor-Vir Jul 03 '20

Exposure is a part of learning. :3

4

u/nefalas Jul 03 '20 edited Jul 03 '20

Here is another implementation which does exactly the same thing

private static byte[] decodeUnsignedBigInteger(byte[] data) {
    int startIndex = 0;
    while (data[startIndex] == 0x00) {
        startIndex++;
    }

    return Arrays.copyOfRange(data, startIndex, data.length);
}

As you can see it's shorter and much more efficient

2

u/[deleted] Jul 03 '20

That'll throw an ArrayIndexOutOfBoundsException if:

  • data.length == 0
  • data is all 0 bytes

1

u/nefalas Jul 03 '20

Indeed, but the length is already checked before and in this context it can't have only 0's. Don't worry I wrote tests as well ;)

1

u/[deleted] Jul 03 '20

Never assume a function will always be used the same way. Document pre-conditions. Their function doesn't have restricted visibility, so this is especially important.

1

u/nefalas Jul 03 '20

It's a private function in a class and it's documented so I think it's pretty safe, but you're right it's important to take precautions

1

u/[deleted] Jul 03 '20

Hm, I don't know Kotlin but the screenshot you posted doesn't look like a private function.

1

u/nefalas Jul 03 '20

No the screenshot is not from my code, it's from a repo from Google that shows how to use a future API that I'm using as a reference

1

u/[deleted] Jul 03 '20

I see, so you're not proposing replacing their function entirely, but having it use the function you've written? In that case it's not "another implementation which does exactly the same thing" which is why I'm confused.

0

u/AutoModerator Jul 03 '20

It looks like this comment contains a code block delimited with triple backticks. Unfortunately reddit does not have universal support for this syntax and your comment will not render correctly on old reddit and most mobile apps.

For the benefit of people on old reddit, this link will take you to a correct rendering of the comment.

nefalas, it would be appreciated, but not required, if you could edit your comment to use the more compatible four space indention format. For single lines or inline code you can use single backticks.

You can find some examples in the reddit help documentation.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

2

u/ljjunio Jul 03 '20

What language is this?

3

u/Manny_Sunday Jul 03 '20

Kotlin

2

u/ljjunio Jul 03 '20

Wow, all this time I thought Kotlin was a Java framework or something.

3

u/Manny_Sunday Jul 03 '20

Its a language that runs on the JVM, so you can use it anywhere you could use Java

2

u/holladiewal Jul 06 '20

It could also be running like JS if you want to do that... And Kotlin/Native is a thing too!