TL;　DR;

CLIだけで操作するマシン単体では認証が通らない
Webブラウザが使えるマシンにもSDKを入れて、そこでブラウザ経由での認証をしなければならない
--no-launch-browserオプションが必要

経緯

Google Cloud SDK (version 377.0.0)をインストールしたGCEインスタンス内でloginコマンドをしたら、見慣れないことを言われた。

$ gcloud auth login

 You are authorizing gcloud CLI without access to a web browser. Please run the following command on a machine with a web browser and copy its output back here. Make sure the installed gcloud version is 372.0.0 or newer.

gcloud auth login --remote-bootstrap="https://accounts.google.com/o/oauth2/auth?response_type=code&client_id=xxxxxxxxx.apps.googleusercontent.com&scope=openid+https%3A%2F%2Fwww.googleapis.com%2Fauth%2Fuserinfo.email+https%3A%2F%2Fwww.googleapis.com%2Fauth%2Fcloud-platform+https%3A%2F%2Fwww.googleapis.com%2Fauth%2Fappengine.admin+https%3A%2F%2Fwww.googleapis.com%2Fauth%2Fcompute+https%3A%2F%2Fwww.googleapis.com%2Fauth%2Faccounts.reauth&state=hogehoge2&access_type=offline&code_challenge=fugafuga&code_challenge_method=S256&token_usage=remote"

Enter the output of the above command: ###←入力待ち状態

一旦今のコマンドを停止させて、出力されたコマンドを別途コマンドプロンプト(Windows 10にWSLで立ち上げたubuntu 18.04)に入力してもエラー

$ gcloud auth login --remote-bootstrap="https://accounts.google.com/o/oauth2/auth?response_type=code&client_id=xxxxxxxxx.apps.googleusercontent.com&scope=openid+https%3A%2F%2Fwww.googleapis.com%2Fauth%2Fuserinfo.email+https%3A%2F%2Fwww.googleapis.com%2Fauth%2Fcloud-platform+https%3A%2F%2Fwww.googleapis.com%2Fauth%2Fappengine.admin+https%3A%2F%2Fwww.googleapis.com%2Fauth%2Fcompute+https%3A%2F%2Fwww.googleapis.com%2Fauth%2Faccounts.reauth&state=hogehoge2&access_type=offline&code_challenge=fugafuga&code_challenge_method=S256&token_usage=remote"

ERROR: (gcloud.auth.login) Cannot launch browser. Please run this command on a machine where gcloud can launch a web browser.

出力されているURL(--remote-bootstrapのパラメータ)をブラウザに入力しても400:invalid_request

ちなみに version 376.0.0の入ったインスタンスで実行した場合は、URLが出力されてそのURLから直接ブラウザ上でのGoogleアカウント認証が可能。

対応

$ gcloud auth login　--no-launch-browser

オプションを付けなかったらどうなるか
コマンドプロンプトから直接Webブラウザにアクセスできる環境にて、gcloudコマンドを実行する必要がある。
今回のケースだと

GCEインスタンス内で $ gcloud auth login実行(入力待ち状態になる)
出力されたコマンドを、Windowsのコマンドプロンプトで(WSLのubuntuではだめ)実行
ブラウザ上でGoogleアカウント認証が行われる
認証が通ると、Windowsのコマンドプロンプトに新たなコマンドが出力される
出力されたコマンドを、GCEインスタンスで　Enter the output of the above command: にコマンドを入力する
認証完了

WSL環境ではだめというのがまた困った話で、操作している端末でgcloudコマンド実行が必須になった。これまでであれば発行されたURLさえあればよかった。

正直かなり困っている

あまりに困ったので勢いだけで記事を書き上げてしまった。
更新: オプションを付けることで解消できていたが書くのを忘れていた