Este error esta relacionado como comentabamos arriba con la firma de tu app , existen dos tipos de SHA1 , el de debug y el de release, el de debug lo podes encontrar de la siguiente forma
te vas a la solapa de la parte arriba a la derecha y clickas gradle - tu proyecto - tasks - signingReport
Luego abajo te aparecera tu SHA1 (este es el de debug , imagen derecha)
Ahora, en tu build.gradle te dice el paquete con el que deberias firmar en la Consola de Firebase.
Para obtener el SHA1 de produccion o Release, abris la terminal en el android studio y haces lo siguiente, te posicionas en la carpeta bin que viene con el SDK , generalmente la encuentras en la carpeta javac
(usualmente en C:\Program Files\Java\jdk1.6.0_14\bin
) . Luego escribes lo siguiente
keytool -list -v -keystore {keystore_name} -alias {alias_name}
por ejemplo
keytool -list -v -keystore C:\Usuario\tu_usuario\Desktop\prueba.jks -alias prueba
El SHA1 de produccion deberia ser el que usarias cuando tu app este en el PlayStore