Cleaned everything:

emacs -Q: get into small buffer for lisp eval

try to set via set-variable: does not find gnutls-algorithm-priority 
(only var starting with gnutls is gnutls-min-prime-bits)

do customize-group gnutls: there the variable gnutls-algorithm-priority 
is shown and set to nil

change it to NORMAL:-VERS-TLS1.3

run package-initialize: no problem

run package-refresh-contents: no problem

install undo-tree via package-install ret undo-tree ret: no problem

  On 19.07.19 14:33, Tim Cross wrote:
> What happens if you do
>
> emacs -Q
>
> set the gnutls-algorithm-priority (using customize-group or set-variable)
>
> and then
>
> M-x customize-group gnutls
>
> M-x package-initialise
> M-x package-refresh-contents
>
> I get a failed to download 'gnu' archive error. If I try to install 
> the delight package (also a dependency of use-package) I get the bad 
> response error.
>
> The issue is definitely TLS related, but not sure if it is client or 
> server end. When I set the perferred algorithm variable, the 
> connections to MELPA fail as well. Without setting that variable (i.e. 
> set to nil) the connections to MELPA work fine and only ELPA fails.
>
> Tim
>
>
>
> On Fri, 19 Jul 2019 at 22:15, Lennard Henze <henzelen@hu-berlin.de 
> <mailto:henzelen@hu-berlin.de>> wrote:
>
>     Hey, I just double checked to not cause unnecessary confusion:
>
>     Crated new user on arch to get empty home:
>
>     used same .emacs as before, but without (setq
>     gnutls-algorithm-priority "NORMAL:-VERS-TLS1.3"). After refreshing
>     package list i can find undo-tree in gnu repos. When i try to
>     install get the same bad request bug.
>
>     After adding the line (setq gnutls-algorithm-priority
>     "NORMAL:-VERS-TLS1.3")
>
>     use-package downloads the package properly at startup and
>     everything works fine.
>
>     Can i provide additional debug info?
>     Still not sure tho if its some dumb mistake in my os.
>
>     On 19.07.19 14:09, Tim Cross wrote:
>>     Yep, checked and it made no difference. Did get a little more wrt
>>     error info
>>
>>     gnutls.el: (err=[-50] The request is invalid.) boot: (:priority
>>     "NORMAL:-VERS-TLS1.3" :hostname melpa.org <http://melpa.org>
>>     :loglevel 0 :min-prime-bits 256 :trustfiles
>>     (/etc/ssl/certs/ca-certificates.crt) :crlfiles nil :keylist nil
>>     :verify-flags nil :verify-error nil :callbacks nil)
>>
>>     Also tried with TLS 1.2, same error.
>>
>>
>>
>>     On Fri, 19 Jul 2019 at 22:02, Noam Postavsky <npostavs@gmail.com
>>     <mailto:npostavs@gmail.com>> wrote:
>>
>>         Robert Pluim <rpluim@gmail.com <mailto:rpluim@gmail.com>> writes:
>>
>>         >     Noam> Does (setq gnutls-algorithm-priority
>>         "NORMAL:-VERS-TLS1.3") help?  If
>>         >     Noam> yes, this is likely Bug#34341 (should already be
>>         fixed already in
>>         >     Noam> emacs-26, and the 26.2.90 pretest).
>>         >
>>         > elpa.gnu.org <http://elpa.gnu.org> uses TLS1.2, not TLS1.3.
>>         But emacs-27 has a bunch of
>>         > changes in its TLS handling that might improve matters.
>>
>>         Hmm, it does.  On the other hand, Lennard told me [Lennard,
>>         please use
>>         "Reply All" next time so your response goes to the bug list]
>>         that (setq
>>         gnutls-algorithm-priority "NORMAL:-VERS-TLS1.3") did actually
>>         help.
>>
>>         Tim, can you check the gnutls-algorithm-priority workaround too?
>>
>>
>>
>>     -- 
>>     regards,
>>
>>     Tim
>>
>>     --
>>     Tim Cross
>>
>
>
> -- 
> regards,
>
> Tim
>
> --
> Tim Cross
>